# Faulty Keyboard
**Difficulty:** EASY
[External](https://leetcode.com/problems/faulty-keyboard)
Canonical: https://scaleengineer.com/dsa/problems/faulty-keyboard
**Data structures:** String
**Companies:** [Samsung](https://scaleengineer.com/companies/samsung)
---
## Problem
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
## Brute-force Simulation with StringBuilder
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public String faultyKeyboard(String s) {
        StringBuilder result = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c == 'i') {
                result.reverse();
            } else {
                result.append(c);
            }
        }
        return result.toString();
    }
}
```
### 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.

## Optimized Simulation with a Deque
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.
**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.
**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.
### Explanation
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.

```java
import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public String faultyKeyboard(String s) {
        Deque<Character> deque = new ArrayDeque<>();
        boolean reversed = false;

        for (char c : s.toCharArray()) {
            if (c == 'i') {
                reversed = !reversed;
            } else {
                if (reversed) {
                    deque.addFirst(c);
                } else {
                    deque.addLast(c);
                }
            }
        }

        StringBuilder result = new StringBuilder();
        if (reversed) {
            while (!deque.isEmpty()) {
                result.append(deque.removeLast());
            }
        } else {
            while (!deque.isEmpty()) {
                result.append(deque.removeFirst());
            }
        }
        return result.toString();
    }
}
```
### 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.

# Solutions
### Java

```java
class 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 (); } }
```

### CPP

```cpp
class 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 ; } };
```

### Python

```python
class 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 )
```