**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) —

**GD Star Rating***loading...*

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