algoadvance

Leetcode 2810. Faulty Keyboard

Problem Statement

You are given a string s that represents the text typed into a faulty keyboard where certain keys are “stuck”. Specifically, any character that appears consecutively more than once should be treated as if it was typed only once. Return the final string after removing consecutive duplicates.

Clarifying Questions

Before proceeding with the solution, let’s clarify some essential points:

  1. Case Sensitivity: Should the comparison be case-sensitive (i.e., ‘a’ and ‘A’ are distinct)?
  2. Constraints: Are there any constraints on the length of the string s?

Assuming comparison is case-sensitive and given no specific constraints:

Strategy

  1. Iterate over the String: Traverse through the string, character by character.
  2. Check Consecutive Duplicates: Add the character to the result if it is not the same as the last character added to the result.
  3. Construct the Result: Use a new string to store the filtered result.

Code

#include <iostream>
#include <string>

std::string removeFaultyKeys(const std::string& s) {
    if (s.empty()) return "";

    std::string result;
    result.reserve(s.size()); // Reserve space to avoid multiple reallocations
    
    char lastChar = '\0';
    for (char c : s) {
        if (c != lastChar) {
            result += c;
            lastChar = c;
        }
    }
    
    return result;
}

int main() {
    std::string input;
    std::cout << "Enter the string typed on the faulty keyboard: ";
    std::getline(std::cin, input);
    
    std::string output = removeFaultyKeys(input);
    std::cout << "Corrected string: " << output << std::endl;

    return 0;
}

Time Complexity

The time complexity of the solution is O(n), where n is the length of the input string s. We are iterating through the string once and performing constant-time checks and operations for each character.

Explanation

  1. Initialization: We initialize an empty result string and a lastChar variable to keep track of the last added character.
  2. Iteration: For each character in the input string:
    • Compare it with the last added character.
    • If it is different, append it to the result string and update lastChar.
  3. Output: The result string is built incrementally, ensuring that consecutive duplicates are removed efficiently.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI