Definition
- Backspace String Compare – determine if two strings produce the same result after applying backspace (#) deletions.
- Stack approach – simulate typing into a
StringBuilder; on#remove the last character; compare final strings. - Two-pointer approach – scan both strings from right to left; skip characters consumed by backspaces using a counter; compare surviving characters.
- Skip counter – each
#increments skip; each normal character with positive skip is consumed and decrements skip. - Complexity – O(n + m) time; O(1) space for the two-pointer version.
Rajesh and Priya at National Bank of India each typed a reference code into a terminal where # means backspace. Instead of rebuilding both codes, Rajesh reads each code backward. Every time he hits a backspace marker, he skips the next real character. He compares the surviving characters from both codes one by one.
Understanding the Concepts
What is the Backspace String Compare problem?
Given two strings that may contain # characters representing backspaces, determine whether they are equal after all backspaces are applied. For example, "ab#c" produces "ac" and "ad#c" also produces "ac", so they are equal.
package com.bank.core;
public class BackspaceCompare {
// Stack-based approach (O(n) space)
public static boolean compareStack(String s, String t) {
return build(s).equals(build(t));
}
private static String build(String s) {
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
if (c == '#') {
if (sb.length() > 0) sb.deleteCharAt(sb.length() - 1);
} else {
sb.append(c);
}
}
return sb.toString();
}
public static void main(String[] args) {
System.out.println(compareStack("ab#c", "ad#c")); // true
System.out.println(compareStack("ab##", "c#d#")); // true
System.out.println(compareStack("a#c", "b")); // false
}
}
true
true
false
How does the constant-space two-pointer approach work?
A backspace deletes characters to its left, so reading right to left lets you account for every deletion as you encounter it. Place a pointer at the end of each string. For each string, use a skip counter: when you see #, increment skip and move left; when you see a normal character with positive skip, decrement skip and move left (the character is consumed); stop when you reach a surviving character (skip is zero and the character is not #).
Compare the two surviving characters. If they differ, the strings are not equal. If both pointers run off the start together, the strings are equal.
package com.bank.core;
public class BackspaceTwoPointers {
public static boolean compare(String s, String t) {
int i = s.length() - 1;
int j = t.length() - 1;
while (i >= 0 || j >= 0) {
i = nextValid(s, i);
j = nextValid(t, j);
if (i >= 0 && j >= 0) {
if (s.charAt(i) != t.charAt(j)) return false;
} else if (i >= 0 || j >= 0) {
return false; // one has chars left, the other does not
}
i--;
j--;
}
return true;
}
private static int nextValid(String s, int idx) {
int skip = 0;
while (idx >= 0) {
if (s.charAt(idx) == '#') { skip++; idx--; }
else if (skip > 0) { skip--; idx--; }
else break;
}
return idx;
}
public static void main(String[] args) {
System.out.println(compare("ab#c", "ad#c")); // true
System.out.println(compare("ab##", "c#d#")); // true
System.out.println(compare("a#c", "b")); // false
}
}
true
true
false
Why scan from right to left?
A backspace affects characters to its left, not to its right. If you scan left to right, you do not know whether the current character will be deleted by a future backspace until you have read the rest of the string. Scanning right to left means you encounter backspaces before the characters they delete, so you can skip the correct characters immediately.
How does the skip counter work?
The skip counter tracks pending backspaces. Each # increments it. Each normal character with a positive skip counter is consumed (deleted) and decrements the counter. The helper stops when it finds a normal character with skip equal to zero, which is a surviving character.
package com.bank.core;
public class SkipCounterTrace {
public static void main(String[] args) {
String s = "abc##d";
int idx = s.length() - 1;
int skip = 0;
while (idx >= 0) {
char c = s.charAt(idx);
if (c == '#') {
skip++;
System.out.println("idx=" + idx + " '#' skip=" + skip);
} else if (skip > 0) {
skip--;
System.out.println("idx=" + idx + " '" + c + "' consumed, skip=" + skip);
} else {
System.out.println("idx=" + idx + " '" + c + "' survives");
}
idx--;
}
}
}
idx=5 'd' survives
idx=4 '#' skip=1
idx=3 '#' skip=2
idx=2 'c' consumed, skip=1
idx=1 'b' consumed, skip=0
idx=0 'a' survives
What is the tricky termination condition?
The two strings can have different lengths and different numbers of backspaces, so the pointers rarely move in sync. After each skip, one pointer might be off the start while the other still points at a surviving character. This means the final strings differ in length. The comparison must handle the case where only one pointer is still valid.
package com.bank.core;
public class TerminationEdge {
public static boolean compare(String s, String t) {
int i = s.length() - 1, j = t.length() - 1;
while (i >= 0 || j >= 0) {
i = skip(s, i); j = skip(t, j);
if (i >= 0 && j >= 0) { if (s.charAt(i) != t.charAt(j)) return false; }
else if (i >= 0 || j >= 0) return false; // one still has chars
i--; j--;
}
return true;
}
private static int skip(String s, int idx) {
int sk = 0;
while (idx >= 0) {
if (s.charAt(idx) == '#') { sk++; idx--; }
else if (sk > 0) { sk--; idx--; }
else break;
}
return idx;
}
public static void main(String[] args) {
// "a" after backspaces vs "" after backspaces
System.out.println(compare("a", "b#")); // false ("a" vs "")
}
}
false
What are the edge cases?
Edge cases include empty strings, strings that are entirely backspaces, strings where backspaces outnumber characters, and strings with consecutive backspaces.
package com.bank.core;
public class BackspaceEdgeCases {
public static boolean compare(String s, String t) {
int i = s.length() - 1, j = t.length() - 1;
while (i >= 0 || j >= 0) {
i = skip(s, i); j = skip(t, j);
if (i >= 0 && j >= 0) { if (s.charAt(i) != t.charAt(j)) return false; }
else if (i >= 0 || j >= 0) return false;
i--; j--;
}
return true;
}
private static int skip(String s, int idx) {
int sk = 0;
while (idx >= 0) {
if (s.charAt(idx) == '#') { sk++; idx--; }
else if (sk > 0) { sk--; idx--; }
else break;
}
return idx;
}
public static void main(String[] args) {
System.out.println("Both empty: " + compare("", "")); // true
System.out.println("All backspace: " + compare("###", "##")); // true (both empty)
System.out.println("Extra backspace: " + compare("a###", "")); // true
}
}
Both empty: true
All backspace: true
Extra backspace: true
How do the two approaches compare?
| Feature | Stack/StringBuilder | Two-pointer (right to left) |
|---|---|---|
| Time | O(n + m) | O(n + m) |
| Space | O(n + m) | O(1) |
| Clarity | Very simple | More complex |
| When to use | Default choice | When constant space required |
The stack approach is easier to get right and is perfectly acceptable unless the interviewer specifically asks for constant space.
What is the banking use case?
At National Bank of India, a legacy entry terminal records every keystroke including corrections where # represents the backspace key. During reconciliation, Rajesh must decide whether two operators ended up entering the same final transaction reference code even though their raw keystroke logs look different due to corrections. The logs are long and run on memory-constrained infrastructure, so the right-to-left two-pointer comparison does it in constant space.
package com.bank.service;
public class KeystrokeReconciliation {
public static boolean sameResult(String log1, String log2) {
int i = log1.length() - 1, j = log2.length() - 1;
while (i >= 0 || j >= 0) {
i = skip(log1, i); j = skip(log2, j);
if (i >= 0 && j >= 0) { if (log1.charAt(i) != log2.charAt(j)) return false; }
else if (i >= 0 || j >= 0) return false;
i--; j--;
}
return true;
}
private static int skip(String s, int idx) {
int sk = 0;
while (idx >= 0) {
if (s.charAt(idx) == '#') { sk++; idx--; }
else if (sk > 0) { sk--; idx--; }
else break;
}
return idx;
}
public static void main(String[] args) {
String rajeshLog = "SAV20#01";
String priyaLog = "SAV201#1";
System.out.println("Same result: " + sameResult(rajeshLog, priyaLog));
}
}
Same result: true
Visual Overview
Backspace String Compare: Two Pointers from the End ════════════════════════════════════════════════════ s = "ab#c" t = "ad#c" s pointer (right to left): idx=3 'c' → survives idx=2 '#' → skip=1 idx=1 'b' → consumed (skip=0) idx=0 'a' → survives Result: "ac" t pointer (right to left): idx=3 'c' → survives idx=2 '#' → skip=1 idx=1 'd' → consumed (skip=0) idx=0 'a' → survives Result: "ac" Compare survivors: c==c ✓, a==a ✓ → Equal!
Key Takeaway
Comparing two strings with backspace characters comes down to a key observation: a backspace deletes characters to its left, so reading from right to left lets you account for every deletion as you encounter it. The constant-space approach uses two pointers and a skip counter for each string, landing on surviving characters and comparing them one by one.
The skip counter is the heart of the algorithm: each # increments it, each normal character with positive skip is consumed and decrements it, and the helper stops when it finds a normal character with zero skip. The tricky part is the termination condition where one pointer runs off the start while the other still has surviving characters, meaning the final strings differ in length.
The stack-based approach that rebuilds both strings is simpler to code and perfectly acceptable unless constant space is specifically required. Both run in O(n + m) time.
In the banking project at National Bank of India, Rajesh uses the two-pointer approach to reconcile keystroke logs from two operators who may have typed different corrections but ended up with the same final reference code, running in constant space on memory-constrained infrastructure.
Remember one sentence: scan from right to left with a skip counter, compare surviving characters in lockstep, and handle the case where one string runs out before the other.
---