Faulty Keyboard - Solution & Explanation
Problem Statement
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 <= 100sconsists of lowercase English letters.s[0] != 'i'
Approach Overview
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 1: Stack-Based Approach
Utilize a stack data structure to manage the characters. When encountering 'i', reverse the current stack list.
This solution iterates through the input string. When character 'i' is encountered, it reverses the current stored characters in the result array. This is achieved by the reverse function which swaps elements symmetrically.
Complexity
Time Complexity: O(n^2) due to repeated string reversals; Space Complexity: O(n).
Approach 2: Two-Pointer Approach
Avoid string reversing by cleverly tracking the insertion position using a two-pointer technique, diving into the array-based manipulation.
In this C solution, two pointers (left and right) are used to control the direction of writing. Upon encountering 'i', the direction in which text is written is switched. This avoids reversing the string directly.
Complexity
Time Complexity: O(n); Space Complexity: O(n).
Approach 3: Simulation
We directly simulate the keyboard input process, using a character array t to record the text on the screen, initially t is empty.
For each character c in string s, if c is not the character 'i', then we add c to the end of t; otherwise, we reverse all characters in t.
The final answer is the string composed of characters in t.
The time complexity is O(n^2), and the space complexity is O(n), where n is the length of string s.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Stack-Based Approach | Time Complexity: O(n^2) due to repeated string reversals; Space Complexity: O(n). |
| Two-Pointer Approach | Time Complexity: O(n); Space Complexity: O(n). |
| Simulation | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Leetcode 2810 Faulty Keyboard Hindi • ThinkCode • 437 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Faulty Keyboard easy or hard?
Faulty Keyboard Python/Java solution
How to solve Faulty Keyboard in O(n)?
What is the best approach for Faulty Keyboard?
Is Faulty Keyboard asked at Google/Amazon/Meta?
What data structure is used in Faulty Keyboard?
What is the time complexity of Faulty Keyboard?
Ready to solve this problem?
Practice Faulty Keyboard with our built-in code editor and test cases.
Practice on FleetCode