Faulty Keyboard

Easy

#2514Time: O(N^2), where N is the length of the input string `s`. In the worst-case scenario, each 'i' character can trigger a reversal of the `StringBuilder`. Reversing a `StringBuilder` of length `k` takes O(k) time. Since `k` can grow up to N, and we might have up to N/2 'i's, the total time complexity becomes quadratic.Space: O(N), where N is the length of the input string `s`. This space is used by the `StringBuilder` to store the resulting string, which can have a length up to N.1 company

Data structures

String

Companies

Samsung

Prompt

Your laptop keyboard is faulty, and whenever you type a character 'i' on it, it reverses the string that you have written. Typing other characters works as expected.

You are given a 0-indexed string s, and you type each character of s using your faulty keyboard.

Return the final string that will be present on your laptop screen.

Example 1:

Input: s = "string"
Output: "rtsng"
Explanation: 
After typing first character, the text on the screen is "s".
After the second character, the text is "st". 
After the third character, the text is "str".
Since the fourth character is an 'i', the text gets reversed and becomes "rts".
After the fifth character, the text is "rtsn". 
After the sixth character, the text is "rtsng". 
Therefore, we return "rtsng".

Example 2:

Input: s = "poiinter"
Output: "ponter"
Explanation: 
After the first character, the text on the screen is "p".
After the second character, the text is "po". 
Since the third character you type is an 'i', the text gets reversed and becomes "op". 
Since the fourth character you type is an 'i', the text gets reversed and becomes "po".
After the fifth character, the text is "pon".
After the sixth character, the text is "pont". 
After the seventh character, the text is "ponte". 
After the eighth character, the text is "ponter". 
Therefore, we return "ponter".

Constraints:

1 <= s.length <= 100
s consists of lowercase English letters.
s[0] != 'i'

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We maintain a string, and for each character in the input, we either append it or, if the character is 'i', we reverse the entire string built so far. Using a StringBuilder in Java is convenient for this, as it is mutable and has a built-in reverse() method.

Algorithm

Initialize an empty StringBuilder called result.
Iterate through each character c of the input string s.
If c is equal to 'i':
- Reverse the current content of the result StringBuilder using its reverse() method.
If c is not 'i':
- Append c to the end of the result StringBuilder.
After the loop finishes, convert the result StringBuilder to a string and return it.

Walkthrough

The brute-force simulation is the most straightforward way to solve the problem. We use a mutable string data structure, like Java's StringBuilder, to construct the output string step-by-step.

We iterate through the input string s from left to right. For each character, we check if it's the faulty key 'i'.

If the character is not 'i', we perform a standard append operation to the end of our StringBuilder.
If the character is 'i', it triggers a reversal of all the text typed so far. We achieve this by calling the reverse() method on our StringBuilder.

After processing all characters in s, the StringBuilder holds the final state of the text on the screen. We then convert it to a standard String and return it. While this method is easy to understand, its performance suffers because the reversal operation's cost increases as the string grows.

1class Solution {2    public String faultyKeyboard(String s) {3        StringBuilder result = new StringBuilder();4        for (char c : s.toCharArray()) {5            if (c == 'i') {6                result.reverse();7            } else {8                result.append(c);9            }10        }11        return result.toString();12    }13}

Complexity

Time

O(N^2), where N is the length of the input string `s`. In the worst-case scenario, each 'i' character can trigger a reversal of the `StringBuilder`. Reversing a `StringBuilder` of length `k` takes O(k) time. Since `k` can grow up to N, and we might have up to N/2 'i's, the total time complexity becomes quadratic.

Space

O(N), where N is the length of the input string `s`. This space is used by the `StringBuilder` to store the resulting string, which can have a length up to N.

Trade-offs

Pros

Very simple and easy to implement.
Directly follows the logic from the problem description.

Cons

The time complexity is quadratic, which can be slow for larger inputs (though acceptable for the given constraints).
Repeatedly reversing a growing string is an inefficient operation.

A more efficient approach avoids the costly O(N) reversal operation by using a Deque (Double-Ended Queue). A Deque allows for constant-time additions at both the front and the back. We can simulate the string reversal by simply changing the end at which we add new characters. A boolean flag tracks whether the string is currently 'reversed'. When a non-'i' character is typed, we add it to the back of the deque if the state is normal, and to the front if the state is 'reversed'. An 'i' simply flips the state flag. This makes each step an O(1) operation.

Algorithm

Initialize an empty Deque<Character> (e.g., ArrayDeque) and a boolean flag isReversed to false.
Iterate through each character c of the input string s.
If c is 'i':
- Flip the isReversed flag: isReversed = !isReversed.
If c is not 'i':
- If isReversed is false, add the character to the back of the deque: deque.addLast(c).
- If isReversed is true, add the character to the front of the deque: deque.addFirst(c).
After the loop, create a StringBuilder to build the final string.
If isReversed is false, poll characters from the front of the deque (pollFirst) and append them to the StringBuilder.
If isReversed is true, poll characters from the back of the deque (pollLast) and append them to the StringBuilder.
Return the resulting string.

Walkthrough

This optimized approach recognizes that physically reversing the string repeatedly is inefficient. The core idea is that appending a character to a reversed string is equivalent to prepending the character to the original string. This behavior can be efficiently modeled using a Deque.

We maintain a Deque<Character> and a boolean flag, isReversed, initialized to false. We iterate through the input string s:

When we see an 'i', we don't touch the deque. We simply flip the isReversed flag. This O(1) operation acts as a 'virtual' reversal.
When we see any other character, we check the isReversed flag. If it's false, we are in the normal state, so we append the character to the end of the deque (addLast). If isReversed is true, we are in the reversed state, so we add the character to the front of the deque (addFirst). Both addLast and addFirst are O(1) operations.

After processing all characters, the deque contains the correct characters. To form the final string, we check the final state of isReversed. If it's false, we build the string by polling from the deque's front. If it's true, the sequence in the deque is effectively reversed, so we build the string by polling from the deque's back. This entire process has a linear time complexity.

1import java.util.Deque;2import java.util.ArrayDeque;3 4class Solution {5    public String faultyKeyboard(String s) {6        Deque<Character> deque = new ArrayDeque<>();7        boolean reversed = false;8 9        for (char c : s.toCharArray()) {10            if (c == 'i') {11                reversed = !reversed;12            } else {13                if (reversed) {14                    deque.addFirst(c);15                } else {16                    deque.addLast(c);17                }18            }19        }20 21        StringBuilder result = new StringBuilder();22        if (reversed) {23            while (!deque.isEmpty()) {24                result.append(deque.removeLast());25            }26        } else {27            while (!deque.isEmpty()) {28                result.append(deque.removeFirst());29            }30        }31        return result.toString();32    }33}

Complexity

Time

O(N), where N is the length of the input string `s`. We iterate through the string once. All operations inside the loop (adding to deque, flipping a boolean) and the final string construction are O(1) per character, leading to a total linear time complexity.

Space

O(N), where N is the length of the input string `s`. The `Deque` can store up to N characters.

Trade-offs

Pros

Optimal time complexity of O(N).
Efficiently handles the logic by avoiding actual string reversals.
Scales well even for larger inputs beyond the problem's constraints.

Cons

Slightly more complex to conceptualize than the brute-force approach.
Uses a more advanced data structure (Deque) which might be less familiar to beginners.

Solutions

Solution

1class Solution { public String finalString ( String s ) { StringBuilder t = new StringBuilder (); for ( char c : s . toCharArray ()) { if ( c == 'i' ) { t . reverse (); } else { t . append ( c ); } } return t . toString (); } }

1class Solution { public: string finalString ( string s ) { string t ; for ( char c : s ) { if ( c == 'i' ) { reverse ( t . begin (), t . end ()); } else { t . push_back ( c ); } } return t ; } };

1class Solution : def finalString ( self , s : str ) -> str : t = [] for c in s : if c == "i" : t = t [:: - 1 ] else : t . append ( c ) return "" . join ( t )

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem