Compare Strings With Deletions
Company: N/A
Role: Backend Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given two strings `s` and `t`. Each string may contain lowercase letters and the special character `#`. A `#` deletes the closest non-deleted character immediately before it, if such a character exists; otherwise it has no effect.
Return whether the two strings are equal after all deletions are applied.
You must implement the comparison without using extra space proportional to the input size. Aim for `O(1)` auxiliary space.
Example:
```text
Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both strings become "ac".
```
```text
Input: s = "a#c", t = "b"
Output: false
Explanation: The first string becomes "c", while the second becomes "b".
```
Quick Answer: This question evaluates string processing and algorithmic optimization skills, specifically handling simulated deletions (backspace behavior) and performing comparisons under a strict auxiliary space constraint.
Return whether two strings are equal after # deletes the previous non-deleted character, using O(1) auxiliary space.
Constraints
- Strings contain lowercase letters and #
Examples
Input: ('ab#c', 'ad#c')
Expected Output: True
Explanation: Both become ac.
Input: ('a#c', 'b')
Expected Output: False
Explanation: Different results.
Input: ('###', '')
Expected Output: True
Explanation: Deletes past start.
Input: ('xywrrmp', 'xywrrmu#p')
Expected Output: True
Explanation: Equal after deletion.
Hints
- Scan backwards while counting pending deletions.