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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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'

Solution

Method 1 – Simulation with StringBuilder/Deque

Intuition

We process each character in the string. If the character is ‘i’, we reverse the current result. Otherwise, we append the character. Since ‘i’ can appear multiple times, we need to reverse efficiently. For small strings, direct reversal is fast enough.

Approach

  1. Initialize an empty result (string, StringBuilder, or list).
  2. Iterate through each character in the input string s:
    • If the character is ‘i’, reverse the result.
    • Otherwise, append the character to the result.
  3. Return the final result as a string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    string finalString(string s) {
        string ans;
        for (char c : s) {
            if (c == 'i') reverse(ans.begin(), ans.end());
            else ans += c;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func finalString(s string) string {
    ans := []byte{}
    for i := 0; i < len(s); i++ {
        if s[i] == 'i' {
            for l, r := 0, len(ans)-1; l < r; l, r = l+1, r-1 {
                ans[l], ans[r] = ans[r], ans[l]
            }
        } else {
            ans = append(ans, s[i])
        }
    }
    return string(ans)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public String finalString(String s) {
        StringBuilder ans = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c == 'i') ans.reverse();
            else ans.append(c);
        }
        return ans.toString();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun finalString(s: String): String {
        val ans = StringBuilder()
        for (c in s) {
            if (c == 'i') ans.reverse()
            else ans.append(c)
        }
        return ans.toString()
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def finalString(self, s: str) -> str:
        ans: list[str] = []
        for c in s:
            if c == 'i':
                ans.reverse()
            else:
                ans.append(c)
        return ''.join(ans)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn final_string(s: String) -> String {
        let mut ans = Vec::new();
        for c in s.chars() {
            if c == 'i' {
                ans.reverse();
            } else {
                ans.push(c);
            }
        }
        ans.iter().collect()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    finalString(s: string): string {
        const ans: string[] = [];
        for (const c of s) {
            if (c === 'i') ans.reverse();
            else ans.push(c);
        }
        return ans.join('');
    }
}

Complexity

  • ⏰ Time complexity: O(n^2) in the worst case (if there are many ‘i’s, each causing a reversal), but for small n (≤100), this is acceptable.
  • 🧺 Space complexity: O(n), for storing the result string.