Faulty Keyboard

Difficulty: Easy | Acceptance: 80.20% | Paid: No Topics: String, Simulation

Your laptop keyboard is faulty, and whenever you type a character ‘i’ on it, it reverses the string that has been typed so far. For example, if you type the string “hello”, then type ‘i’, the string becomes “olleh”. If you type more characters after typing ‘i’, they are added to the end of the string as usual.

Given a string s, return the final string that would be displayed on the screen.

• Examples
• Constraints
• Brute Force Simulation
• Deque Approach
• String Concatenation with Reverse Flag

Examples

Input: s = "string"
Output: "rtsng"
Explanation: 
After typing 's', 't', 'r', the string is "str".
After typing 'i', the string becomes "rts".
Then we type 'n' and 'g' to get "rtsng".

Input: s = "poiinter"
Output: "ponter"
Explanation: 
After typing 'p', 'o', the string is "po".
After typing 'i', the string becomes "op".
After typing 'i', the string becomes "po".
Then we type 'n', 't', 'e', 'r' to get "ponter".

Constraints

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

Brute Force Simulation

Intuition Simulate the typing process directly: build the result character by character, reversing the entire string whenever ‘i’ is encountered.

Steps

• Initialize an empty list to build the result
• Iterate through each character in the input string
• If the character is ‘i’, reverse the current result list
• Otherwise, append the character to the result
• Join the list into a string and return

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

Complexity

• Time: O(n²) in the worst case, where n is the length of the string. Each ‘i’ causes a full reversal which takes O(n).
• Space: O(n) for storing the result
• Notes: Simple to implement but inefficient for strings with many ‘i’ characters.

Deque Approach

Intuition Instead of actually reversing, track whether we’re in “reverse mode” and use a deque to efficiently add characters to either the front or back.

Steps

• Initialize an empty deque and a boolean flag to track reverse mode
• Iterate through each character in the input string
• If the character is ‘i’, toggle the reverse mode flag
• Otherwise, add the character to the front of the deque if in reverse mode, or to the back otherwise
• At the end, if in reverse mode, read the deque from back to front; otherwise, read from front to back

from collections import deque

class Solution:
    def finalString(self, s: str) -> str:
        dq = deque()
        reversed = False
        for c in s:
            if c == 'i':
                reversed = not reversed
            else:
                if reversed:
                    dq.appendleft(c)
                else:
                    dq.append(c)
        if reversed:
            return ''.join(reversed(dq))
        return ''.join(dq)

Complexity

• Time: O(n), where n is the length of the string. Each character is processed exactly once with O(1) operations.
• Space: O(n) for the deque
• Notes: Efficient and optimal for this problem. Uses a deque to achieve O(1) insertions at both ends.

String Concatenation with Reverse Flag

Intuition Track whether we’re in reverse mode and build the string by prepending or appending characters accordingly. Reverse once at the end if needed.

Steps

• Initialize an empty string and a boolean flag to track reverse mode
• Iterate through each character in the input string
• If the character is ‘i’, toggle the reverse mode flag
• Otherwise, prepend the character to the result if in reverse mode, or append otherwise
• At the end, if in reverse mode, reverse the entire result string

class Solution:
    def finalString(self, s: str) -> str:
        result = ''
        reversed = False
        for c in s:
            if c == 'i':
                reversed = not reversed
            elif reversed:
                result = c + result
            else:
                result = result + c
        if reversed:
            result = result[::-1]
        return result

Complexity

• Time: O(n²) in the worst case, where n is the length of the string. String concatenation/insertion at the beginning is O(n).
• Space: O(n) for the result string
• Notes: Intuitive but inefficient due to the cost of string concatenation. Similar to the brute force approach.