Teaching Kids Programming – Faulty Keyboard with an Inverse Key (Two Algorithms/Double-ended Queue)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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’

Faulty Keyboard with an Inverse Key

We can just do what we are told to do. The following is the naive implementation. The time complexity is O(N^2) quadratic because of reversing operations. Consider string like “aibicidiei…” where there is an inverse operation every other character. The Space complexity is O(N) due to the usage of an array/list. We append the characters or reverse the current characters in the array, and finally concatenate the characters of the array into the string.

1
2
3
4
5
6
7
8
9

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

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

A better/optimised algorithm would be to flip the status of “inverse”, and append the character to the left or right depending on the flip flag. And finally, reverse if there are odd number of “inverse”

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

class Solution:
    def finalString(self, s: str) -> str:
        flip = False
        arr = deque()
        for i in s:
            if i == 'i':
                flip = not flip
            elif flip:
                arr.appendleft(i)
            else:
                arr.append(i)
        if flip:
            return "".join(list(arr)[::-1])
        return "".join(arr)

class Solution:
    def finalString(self, s: str) -> str:
        flip = False
        arr = deque()
        for i in s:
            if i == 'i':
                flip = not flip
            elif flip:
                arr.appendleft(i)
            else:
                arr.append(i)
        if flip:
            return "".join(list(arr)[::-1])
        return "".join(arr)

The time complexity is O(N) as we are not actually flipping/reversing when we meet the “inverse” operation, and we only inverse once, when there is an odd number of inverses. The space complexity is O(N) due to the usage of a double-ended queue, where we can achieve O(1) constant time appending an item to the left of the queue.

–EOF (The Ultimate Computing & Technology Blog) —