Frontend School

Process String with Backspaces

DSA
easy

Process String with Backspaces

Easy
Stack
String

Overview

In many text editors and messaging apps, users can type characters and use a backspace to delete the last character typed. This problem simulates such a basic text processing functionality. Understanding how to correctly apply operations in sequence, especially deletions, is crucial for building reliable user interfaces. This problem helps evaluate your ability to manage state and apply operations in a Last-In, First-Out (LIFO) manner.

What you need to do / Task

Your task is to implement a function that takes a string s as input. This string can contain lowercase English letters and the '#' character, which represents a backspace. You need to simulate the typing process and return the final string after all backspace operations have been applied.

Specifically:

  1. Iterate through the input string s character by character.
  2. If a character is a lowercase letter, it should be "typed".
  3. If a character is '#', it represents a backspace. If there is at least one character already typed, the last typed character should be "deleted". If there are no characters to delete, the backspace does nothing.
  4. After processing the entire input string, return the resulting string.

Input & output

Input:

  • s: A string consisting of lowercase English letters and '#' characters.

Output:

  • A string representing the final text after all backspace operations have been processed.

Clarifications

  • Empty string input: If s is an empty string, the output should also be an empty string.
  • Consecutive backspaces: Multiple '#' characters will delete preceding characters one by one. If the stack becomes empty, further '#' characters do nothing.
  • Only backspaces: If the input string contains only '#' characters, the output should be an empty string.

Examples

1

Example 1

Input:

s = "ab#c"

Output:

"ac"

Note:

'a' is typed, 'b' is typed. Then '#' deletes 'b'. Finally, 'c' is typed. The resulting string is "ac".

2

Example 2

Input:

s = "a#b#c"

Output:

"c"

Note:

'a' is typed, then '#' deletes 'a'. Stack is empty. 'b' is typed, then '#' deletes 'b'. Stack is empty. 'c' is typed. The resulting string is "c".

3

Example 3

Input:

s = "ab##c"

Output:

"c"

Note:

'a' is typed, 'b' is typed. First '#' deletes 'b'. Second '#' deletes 'a'. Stack is empty. 'c' is typed. The resulting string is "c".

4

Example 4

Input:

s = "abc###d"

Output:

"d"

Note:

'a', 'b', 'c' are typed. First '#' deletes 'c'. Second '#' deletes 'b'. Third '#' deletes 'a'. Stack is empty. 'd' is typed. The resulting string is "d".

Constraints

Constraints & assumptions

  • 1 <= s.length <= 10^5
  • s consists only of lowercase English letters and '#'.

What interviewers evaluate

  • Correctness: Does the solution correctly handle all types of inputs, including edge cases like multiple backspaces, backspaces on empty text, and empty input strings?
  • Algorithm Efficiency: Is the solution optimal in terms of time and space complexity (ideally O(N) time and O(N) space, where N is the length of the input string)?
  • Code Readability & Structure: Is the code clean, well-organized, and easy to understand? Are appropriate data structures used?

Loading editor...