Teaching Kids Programming – Typing Characters with Backspace (Text Editor Algorithm via Stack)

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a string s representing characters typed into an editor, with “<-” representing a backspace, return the current state of the editor.

Constraints
n ≤ 100,000 where n is the length of s
Example 1
Input
s = “abc<-z”
Output
“abz”
Explanation
The “c” got deleted by the backspace.

Example 2
Input
s = “<-x<-z<-”
Output
“”
Explanation
All characters are deleted. Also note you can type backspace when the editor is empty as well.

Hints:
Use stack and pop elements when you get ‘<-‘
Or you can think of traversing string from end to start and maintaining count of backslashes encountered.

Typing Characters with Backspace (Text Editor Algorithm)

We can emulate this process of key typing by using a stack – when we meet a backspace, we remove the top from the stack. And at last step, we concatenate all the characters into a string. When we meet a backspace, if we are checking the next character we have to skip two (jump ahead) characters.

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

class Solution:
    def solve(self, s):
        ans = []
        i = 0
        n = len(s)
        while i < n:
            if i + 1 < n and s[i] == '<' and s[i + 1] == '-':
                if ans:
                    ans.pop()
                i += 2
            else:
                ans.append(s[i])
                i += 1
        return "".join(ans)

class Solution:
    def solve(self, s):
        ans = []
        i = 0
        n = len(s)
        while i < n:
            if i + 1 < n and s[i] == '<' and s[i + 1] == '-':
                if ans:
                    ans.pop()
                i += 2
            else:
                ans.append(s[i])
                i += 1
        return "".join(ans)

Alternatively, we can check previous character, but we have to pop one more characters because “-” is already in the stack.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def solve(self, s):
        ans = []
        for i in range(len(s)):
            if i > 0 and s[i] == '-' and s[i - 1] == '<':
                ans.pop()
                if ans:                
                    ans.pop()                
            else:
                ans.append(s[i])
        return "".join(ans)

class Solution:
    def solve(self, s):
        ans = []
        for i in range(len(s)):
            if i > 0 and s[i] == '-' and s[i - 1] == '<':
                ans.pop()
                if ans:                
                    ans.pop()                
            else:
                ans.append(s[i])
        return "".join(ans)

Another interesting approach would be to split the string by the backspace i.e. “<-” and then concatenate the characters but we have to remove the last character (except the last group) since it will be deleted.

1
2
3
4
5
6
7
8

class Solution:
    def solve(self, s):
        arr = s.split('<-')
        ans = arr[0]
        for i in arr[1:]:
            ans = ans[:-1]
            ans += i
        return ans

class Solution:
    def solve(self, s):
        arr = s.split('<-')
        ans = arr[0]
        for i in arr[1:]:
            ans = ans[:-1]
            ans += i
        return ans

Time/space complexity for all algorithms above are O(N) where N is the number of characters as we iterate over the characters once and we need additional space either stack or array.

–EOF (The Ultimate Computing & Technology Blog) —