LeetCode 2810 - Faulty Keyboard

LeetCode Problem 2810

Difficulty: 🟢 Easy
Topics: String, Simulation

Solution

Problem Understanding

In this problem, we are given a string s that represents characters typed on a faulty keyboard. Most characters behave normally and are appended to the current text on the screen. However, whenever the character 'i' is typed, the keyboard does not insert the character itself. Instead, it immediately reverses the entire string that has already been built.

The task is to simulate this typing process and return the final string that appears on the screen after every character in s has been processed.

For example, if the current text is "abc" and the next typed character is 'i', the text becomes "cba". The character 'i' itself does not remain in the result. If the next typed character is a normal character such as 'd', the text becomes "cbad".

The input consists of a single string s containing only lowercase English letters. The length of the string is at most 100, which is quite small. Because the input size is limited, even less efficient simulation approaches would still work within the constraints. However, the goal is to design a clean and efficient solution.

The constraint s[0] != 'i' guarantees that the very first operation is never a reversal of an empty string. Still, even if it were, reversing an empty string would simply produce another empty string.

Several edge cases are important to think about before implementing the solution. Consecutive 'i' characters can repeatedly reverse the string, which may restore a previous order. A string containing no 'i' characters should remain unchanged. A string where every other character is 'i' requires careful simulation because the direction keeps flipping. Another important detail is that 'i' is never added to the result itself, it only triggers a reversal operation.

Approaches

Brute Force Approach

The most direct way to solve the problem is to simulate the keyboard exactly as described.

We maintain a mutable string representing the current text on the screen. Then we iterate through each character in s.

If the current character is not 'i', we append it to the current string.

If the current character is 'i', we reverse the entire current string.

This approach is straightforward and mirrors the problem statement exactly, which makes it easy to reason about correctness.

However, reversing a string requires traversing the whole string each time. If there are many reversal operations, repeated reversals can become expensive. In the worst case, if the string length were very large, repeatedly reversing could lead to quadratic time complexity.

Even though the actual constraints are small enough that this solution easily passes, it is still useful to analyze a more optimal approach.

Optimal Approach

The key observation is that reversing the entire string repeatedly is expensive because each reversal processes all characters accumulated so far.

Instead of physically reversing the string every time we encounter 'i', we can track the current direction logically.

We maintain a deque and a boolean flag indicating whether we are currently building the string in normal order or reversed order.

When we encounter a normal character:

• If the direction is normal, we append it to the back.
• If the direction is reversed, we append it to the front.

When we encounter 'i', we simply toggle the direction flag instead of reversing the whole structure.

At the end, if the direction is reversed, we reverse the final result once.

This avoids repeated full reversals and reduces the total complexity to linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeated string reversals can become expensive
Optimal	O(n)	O(n)	Uses deque and direction tracking to avoid repeated reversals

Algorithm Walkthrough

Optimal Algorithm

1. Initialize an empty deque to store characters efficiently from both ends.
2. Initialize a boolean variable such as reversed_mode and set it to False. This variable tracks whether the current logical direction is reversed.
3. Iterate through every character in the input string s.
4. For each character:

• If the character is 'i', toggle reversed_mode.

• Otherwise:

• If reversed_mode is False, append the character to the back of the deque.

• If reversed_mode is True, append the character to the front of the deque.

5. After processing all characters:

• If reversed_mode is False, join the deque as is.
• If reversed_mode is True, reverse the deque once before joining.

6. Return the resulting string.

Why it works

The algorithm maintains an important invariant throughout execution: the deque always represents the current screen text, except that its orientation depends on the current direction mode.

Instead of physically reversing the string every time 'i' appears, the algorithm changes how future characters are inserted. Appending to the front while in reversed mode produces the same effect as repeatedly reversing the full string after every toggle.

Because each character is inserted exactly once and the final reversal happens at most once, the algorithm correctly reproduces the keyboard behavior while remaining efficient.

Python Solution

from collections import deque

class Solution:
    def finalString(self, s: str) -> str:
        characters = deque()
        reversed_mode = False

        for ch in s:
            if ch == 'i':
                reversed_mode = not reversed_mode
            else:
                if reversed_mode:
                    characters.appendleft(ch)
                else:
                    characters.append(ch)

        if reversed_mode:
            characters.reverse()

        return "".join(characters)

The implementation begins by creating a deque named characters. A deque is chosen because it supports efficient insertion at both the front and back in constant time.

The variable reversed_mode tracks whether the logical direction is currently reversed.

As we iterate through the input string, every 'i' toggles the direction flag. Normal characters are inserted at either the front or back depending on the current direction.

At the end, if the final direction is reversed, the deque itself is reversed once so that the final ordering matches the expected screen output.

Finally, all characters are joined into a single string and returned.

Go Solution

func finalString(s string) string {
	deque := make([]byte, 0)
	reversedMode := false

	for i := 0; i < len(s); i++ {
		ch := s[i]

		if ch == 'i' {
			reversedMode = !reversedMode
		} else {
			if reversedMode {
				deque = append([]byte{ch}, deque...)
			} else {
				deque = append(deque, ch)
			}
		}
	}

	if reversedMode {
		for left, right := 0, len(deque)-1; left < right; left, right = left+1, right-1 {
			deque[left], deque[right] = deque[right], deque[left]
		}
	}

	return string(deque)
}

The Go implementation follows the same overall logic as the Python version. Since Go does not provide a built in deque structure in the standard library, a byte slice is used instead.

Appending to the back is efficient with append. Appending to the front is implemented with append([]byte{ch}, deque...), which is less efficient than a true deque but still acceptable given the small constraints.

The final reversal is performed manually using a two pointer swap loop.

Because the input length is at most 100, this implementation easily satisfies all performance requirements.

Worked Examples

Example 1

Input:

s = "string"

Step	Character	Action	Current Result
1	s	append to back	"s"
2	t	append to back	"st"
3	r	append to back	"str"
4	i	toggle reverse mode	"str"
5	n	append to front	"nstr"
6	g	append to front	"gnstr"

At the end, reverse mode is active, so we reverse once:

"gnstr" -> "rtsng"

Final answer:

"rtsng"

Example 2

Input:

s = "poiinter"

Step	Character	Action	Current Structure
1	p	append to back	"p"
2	o	append to back	"po"
3	i	toggle reverse mode	"po"
4	i	toggle reverse mode again	"po"
5	n	append to back	"pon"
6	t	append to back	"pont"
7	e	append to back	"ponte"
8	r	append to back	"ponter"

Reverse mode ends as False, so no final reversal is needed.

Final answer:

"ponter"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed once
Space	O(n)	The deque stores the final characters

The optimal solution processes every input character exactly one time. Insertions at the front or back of the deque are constant time operations. At most one final reversal is performed, which is also linear. Therefore, the total running time is O(n).

The auxiliary space complexity is O(n) because we store the resulting characters in the deque.

Test Cases

solution = Solution()

assert solution.finalString("string") == "rtsng"  # Provided example
assert solution.finalString("poiinter") == "ponter"  # Consecutive reversals
assert solution.finalString("abc") == "abc"  # No reversals
assert solution.finalString("abci") == "cba"  # Reverse at end
assert solution.finalString("iabc") == "cba"  # Reverse before adding more characters
assert solution.finalString("ii") == ""  # Multiple reversals with no letters
assert solution.finalString("aib") == "ba"  # Single reversal in middle
assert solution.finalString("abcdefi") == "fedcba"  # Full reversal at end
assert solution.finalString("aii") == "a"  # Double toggle restores order
assert solution.finalString("abid") == "bad"  # Continue after reversal
assert solution.finalString("biiac") == "bac"  # Multiple toggles
assert solution.finalString("z") == "z"  # Minimum length without reversal

Test	Why
"string"	Validates the provided example
"poiinter"	Checks consecutive reversal operations
"abc"	Ensures normal typing works
"abci"	Tests reversal at the very end
"iabc"	Tests starting in reversed mode
"ii"	Ensures repeated reversals work correctly
"aib"	Verifies insertion while reversed
"abcdefi"	Tests reversing a larger accumulated string
"aii"	Ensures double toggle restores direction
"abid"	Checks appending after reversal
"biiac"	Tests multiple direction changes
"z"	Minimum non reversal case

Edge Cases

One important edge case is consecutive 'i' characters. A naive implementation might incorrectly append the character 'i' itself or fail to handle repeated reversals properly. For example, "aii" should end as "a" because the direction toggles twice and returns to normal. The implementation handles this by only toggling the boolean flag and never inserting 'i' into the deque.

Another important edge case is when the string contains no 'i' characters at all. In that situation, the output should exactly match the input because no reversals ever occur. The algorithm naturally handles this because all characters are simply appended to the back.

A third important edge case occurs when the final operation leaves the string in reversed mode. For example, "abci" should produce "cba". Without the final reversal step, the deque would internally contain characters in the opposite orientation. The implementation correctly checks the final state of reversed_mode and performs one final reversal if necessary.

A fourth subtle edge case is handling empty intermediate strings. Even though the constraints guarantee s[0] != 'i', later operations may still reverse an empty structure if previous operations removed all logical content. Reversing an empty deque is safe and produces the correct behavior automatically.