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

#### Bydinesh

May 1, 2022

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.

GD Star Rating

577 words
Last Post: Teaching Kids Programming - Square of a List using Two Pointer Algorithm

Source