Watch 10 video solutions for Faulty Keyboard, a easy level problem involving String, Simulation. This walkthrough by ThinkCode has 425 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 100s consists of lowercase English letters.s[0] != 'i'Problem Overview: You type characters on a keyboard, but the key 'i' is faulty. Instead of being added to the text, it reverses the string typed so far. Given the input string s, simulate the typing process and return the final string.
Approach 1: Stack-Based Simulation (O(n^2) time, O(n) space)
Use a stack or dynamic string buffer to simulate typing. Iterate through the characters of s. For normal characters, push them onto the stack. When you encounter 'i', reverse the current stack contents. Reversal requires popping elements and rebuilding the sequence, which can take O(k) time where k is the current length. In the worst case—multiple 'i' operations—the repeated reversals push the total time to O(n^2). This approach mirrors the problem statement directly and is easy to reason about during an interview.
Approach 2: Two-Pointer / Direction Simulation (O(n) time, O(n) space)
A more efficient simulation avoids physically reversing the string each time. Maintain a direction flag that represents whether the current text is being built normally or reversed. Use a deque-like structure or two-pointer placement strategy: append characters to the back when the direction is normal and to the front when the direction is reversed. When you see 'i', simply toggle the direction flag instead of reversing the data. After processing the entire string, output the characters in the correct order based on the final direction. Each character is inserted exactly once, giving O(n) time complexity with O(n) space.
This problem is primarily about careful simulation of operations on a string. The optimized solution relies on controlling the insertion direction rather than repeatedly reversing the entire sequence.
Recommended for interviews: Start with the stack simulation because it clearly models the faulty keyboard behavior. Then optimize by eliminating repeated reversals using the two-pointer or deque strategy. Interviewers typically expect the O(n) simulation because it demonstrates awareness of hidden costs in repeated string reversals.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-Based Simulation | O(n^2) | O(n) | Straightforward implementation when demonstrating the problem’s mechanics step by step |
| Two-Pointer / Direction Simulation | O(n) | O(n) | Preferred approach for interviews and production due to avoiding repeated reversals |