algoadvance

Leetcode 2810. Faulty Keyboard

Problem Statement

Imagine you are using a keyboard that is faulty. The only type of input it accepts correctly are alphabetical characters. However, for every character it prints, it erroneously includes a duplicate character immediately next to it. Thus, if you input the string “leetcode”, it will print “lleettccooddee”.

Given a string s generated by such a faulty keyboard, your task is to reconstruct the original string that you meant to type.

Clarifying Questions

  1. Input Boundaries: What are the maximum lengths of the input string s?
    • Typically, expect s.length() up to (10^5).
  2. Character Set: Does the input string s only consist of lowercase alphabetical characters here?
    • Yes, we can assume s only consists of lowercase a-z characters.
  3. Edge Cases: What should we return for an empty input string?
    • An empty input string should return an empty output string.

Strategy

The faulty keyboard prints each character twice consecutively. Thus, the solution needs to iterate over the input string, picking every second character to reconstruct the original string.

Code

Here’s the Java code to solve the problem:

public class FaultyKeyboard {
    public static String fixFaultyKeyboard(String s) {
        StringBuilder originalString = new StringBuilder();
        
        // Iterate over the input string, taking every second character
        for (int i = 0; i < s.length(); i += 2) {
            originalString.append(s.charAt(i));
        }
        
        return originalString.toString();
    }

    public static void main(String[] args) {
        String inputString = "lleettccooddee";
        System.out.println(fixFaultyKeyboard(inputString));  // Output: leetcode
    }
}

Time Complexity

The time complexity for this solution is (O(n)), where (n) is the length of the input string s. This is because we are simply iterating through the string once.

Explanation

  1. StringBuilder for Efficiency: Using StringBuilder allows us to efficiently build the result string.
  2. Loop through Every Second Character: By incrementing the index i by 2 in each iteration, we only append the first of every pair of characters to the StringBuilder.
  3. Return the Result: Finally, we convert the StringBuilder to a string and return it as the result.

Example

For an input of s = "lleettccooddee", the output will be "leetcode" because we take the first of every adjacent pair:

Thus, the reconstructed original string is "leetcode".

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