Backspace String Compare asks whether two strings are equal after processing '#' as a backspace. The stack answer takes a minute; the follow-up, O(1) extra space, is what the interviewer is really waiting for.
Push characters onto a list and pop on '#'. Compare the results. Time O(n + m), space O(n + m). State it, then offer to improve the space.
A backspace only affects characters before it, so scan each string from the right. Keep a count of pending backspaces; skip characters while the count is positive. The next character that survives is the next visible character from the right.
def backspace_compare(s, t):
def next_index(x, i):
skip = 0
while i >= 0:
if x[i] == '#':
skip += 1
elif skip:
skip -= 1
else:
break
i -= 1
return i
i, j = len(s) - 1, len(t) - 1
while True:
i, j = next_index(s, i), next_index(t, j)
if i < 0 or j < 0:
return i < 0 and j < 0
if s[i] != t[j]:
return False
i -= 1
j -= 1
Backspaces at the start of a string do nothing, which the skip counter handles because it simply runs past index 0. Strings that are all backspaces become empty and compare equal to each other.
Each index is visited once, so time is O(n + m) and extra space is O(1). The reusable idea is processing from the end when later characters modify earlier ones, which also appears in Merge Sorted Array.
Disclosure: I work on Linkjob AI's coding interview copilot, which suggests follow-ups like this while you practise.