Backspace String Compare solution and explanation
IBM
Google
9 more videos on this problem
LeetCode Backspace String Compare Solution Explained - JavaNick White · 7:42 · 32K views
Backspace String Compare - Leetcode 844 - PythonNeetCodeIO · 14:10 · 23K views
Backspace string compare | Leetcode #844Techdose · 4:54 · 18K views
Backspace String Compare (LeetCode 844) | Full solution with actual examples | Study AlgorithmsNikhil Lohia · 13:24 · 11K views
LeetCode #844 | Backspace String Compare | O(1) Space | No stacksKnowledge Center · 18:11 · 9K views
Leetcode - Backspace String Compare (Python)Timothy H Chang · 4:39 · 4K views
Backspace String Compare - LeetCode #844 | Python, JavaScript, Java, C++CodingNinja · 8:02 · 2K views
Backspace String Compare Java Code | LeetCode 844 | Programming TutorialsProgramming Tutorials · 16:44 · 2K views
844. Backspace String Compare LeetCode (Google Interview Question) JavaScriptdev alex · 3:52 · 881 views
Backspace String Compare | Leetcode 844 | Two Pointer | StringNitesh Nanda · 11:55 · 695 views
The problem
Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.
Note that after backspacing an empty text, the text will continue empty.
Example 1:
Input: s = "ab#c", t = "ad#c" Output: true Explanation: Both s and t become "ac".
Example 2:
Input: s = "ab##", t = "c#d#" Output: true Explanation: Both s and t become "".
Example 3:
Input: s = "a#c", t = "b" Output: false Explanation: s becomes "c" while t becomes "b".
Constraints:
1 <= s.length, t.length <= 200sandtonly contain lowercase letters and'#'characters.
Follow up: Can you solve it in O(n) time and O(1) space?
Approach overview
Problem Overview: Two strings s and t represent text typed into a text editor where the character # acts as a backspace. Each # deletes the previous character if one exists. The task is to determine whether both strings produce the same final text after applying all backspaces.
Approach 1: Using a Stack to Simulate Typing (O(n) time, O(n) space)
This approach directly simulates how a text editor processes characters. Iterate through each string and push characters onto a stack. When a # appears, pop the top element if the stack is not empty. After processing the entire string, the stack contains the final characters in order. Repeat for both strings and compare the resulting sequences. The key insight is that a stack naturally models backspace behavior because it removes the most recently added character. This method is easy to reason about and mirrors the real typing process, but it requires O(n) additional space to store the intermediate characters. Related concepts appear frequently in stack and string problems where operations modify the most recent element.
Approach 2: Two-Pointer Technique (O(n) time, O(1) space)
The optimized approach avoids building the final strings entirely. Instead, scan both strings from right to left using two pointers. Maintain a counter that tracks how many characters should be skipped due to backspaces. When a # is encountered, increase the skip counter. When a normal character appears and the counter is positive, decrement the counter and skip the character. This effectively simulates the backspace effect without storing characters. Continue moving both pointers until valid characters are found, then compare them. If the characters differ, the strings are not equal. This approach processes each character at most once, giving O(n) time complexity while using only O(1) extra space. The technique is a strong example of scanning strings efficiently with two pointers and is often categorized under simulation problems.
Recommended for interviews: Start with the stack simulation because it demonstrates a clear understanding of the problem and is straightforward to implement. Then mention the two-pointer optimization. Interviewers usually expect the constant-space solution since it eliminates the need to construct intermediate strings while keeping the same O(n) runtime.
Approach 1: Using a Stack to Simulate Typing
This approach simulates the typing process using two stacks, one for each string. We iterate over each string, using the stack to build the string as it would appear after considering the backspace characters ('#'). By comparing the final stack representations, we can determine if the two strings are equivalent.
def backspaceCompare(s: str, t: str) -> bool:
def buildFinalString(string: str) -> str:
stack = []
for ch in string:
if ch != '#':
stack.append(ch)
elif stack:
stack.pop()
return ''.join(stack)
return buildFinalString(s) == buildFinalString(t)
# Example usage:
print(backspaceCompare("ab#c", "ad#c")) # True
print(backspaceCompare("ab##", "c#d#")) # True
print(backspaceCompare("a#c", "b")) # Falseimport java.util.Stack;
public class BackspaceStringCompare {
public boolean backspaceCompare(String s, String t) {
return buildFinalString(s).equals(buildFinalString(t));
}
private String buildFinalString(String str) {
Stack<Character> stack = new Stack<>();
for (char ch : str.toCharArray()) {
if (ch != '#') {
stack.push(ch);
} else if (!stack.isEmpty()) {
stack.pop();
}
}
StringBuilder result = new StringBuilder();
while (!stack.isEmpty()) {
result.append(stack.pop());
}
return result.reverse().toString();
}
public static void main(String[] args) {
BackspaceStringCompare solution = new BackspaceStringCompare();
System.out.println(solution.backspaceCompare("ab#c", "ad#c")); // true
System.out.println(solution.backspaceCompare("ab##", "c#d#")); // true
System.out.println(solution.backspaceCompare("a#c", "b")); // false
}
}#include <iostream>
#include <stack>
#include <string>
using namespace std;
string buildFinalString(const string &str) {
stack<char> s;
for (char ch : str) {
if (ch != '#') {
s.push(ch);
} else if (!s.empty()) {
s.pop();
}
}
string result;
while (!s.empty()) {
result += s.top();
s.pop();
}
reverse(result.begin(), result.end());
return result;
}
bool backspaceCompare(string s, string t) {
return buildFinalString(s) == buildFinalString(t);
}
int main() {
cout << backspaceCompare("ab#c", "ad#c") << endl; // true
cout << backspaceCompare("ab##", "c#d#") << endl; // true
cout << backspaceCompare("a#c", "b") << endl; // false
return 0;
}function backspaceCompare(s, t) {
function buildFinalString(str) {
const stack = [];
for (let ch of str) {
if (ch !== '#') {
stack.push(ch);
} else if (stack.length > 0) {
stack.pop();
}
}
return stack.join('');
}
return buildFinalString(s) === buildFinalString(t);
}
// Example usage:
console.log(backspaceCompare("ab#c", "ad#c")); // true
console.log(backspaceCompare("ab##", "c#d#")); // true
console.log(backspaceCompare("a#c", "b")); // false#include <stdio.h>
#include <string.h>
#define MAX_LEN 201
// Helper function to process the string accounting for backspaces
void buildFinalString(const char* str, char* result) {
int j = 0;
for (int i = 0; str[i]; i++) {
if (str[i] != '#') {
result[j++] = str[i];
} else if (j > 0) {
j--;
}
}
result[j] = '\0';
}
int backspaceCompare(char * s, char * t) {
char finalS[MAX_LEN], finalT[MAX_LEN];
buildFinalString(s, finalS);
buildFinalString(t, finalT);
return strcmp(finalS, finalT) == 0;
}
int main() {
printf("%d\n", backspaceCompare("ab#c", "ad#c")); // 1 (true)
printf("%d\n", backspaceCompare("ab##", "c#d#")); // 1 (true)
printf("%d\n", backspaceCompare("a#c", "b")); // 0 (false)
return 0;
}using System;
using System.Collections.Generic;
class Program {
static string BuildFinalString(string str) {
var stack = new Stack<char>();
foreach (char ch in str) {
if (ch != '#') {
stack.Push(ch);
} else if (stack.Count > 0) {
stack.Pop();
}
}
return new string(stack.ToArray());
}
static bool BackspaceCompare(string s, string t) {
return BuildFinalString(s) == BuildFinalString(t);
}
static void Main() {
Console.WriteLine(BackspaceCompare("ab#c", "ad#c")); // true
Console.WriteLine(BackspaceCompare("ab##", "c#d#")); // true
Console.WriteLine(BackspaceCompare("a#c", "b")); // false
}
}This Python solution leverages a list to emulate stack behavior, appending characters unless they're '#', in which case we remove the last element if the list isn't empty. We then compare the two processed strings for equality.
Time Complexity: O(n + m), where n and m are the lengths of s and t.
Space Complexity: O(n + m), due to the stack used to store characters.
Approach 2: Two-Pointer Technique
This approach avoids extra space by using two pointers to traverse the strings backwards. By skipping over characters that are effectively backspaced due to a '#' character, we can compare corresponding positions in each string without actually building the resultant strings.
def backspaceCompare(s: str, t: str) -> bool:
si, ti = len(s) - 1, len(t) - 1
skipS = skipT = 0
while si >= 0 or ti >= 0:
while si >= 0:
if s[si] == '#':
skipS += 1
si -= 1
elif skipS > 0:
skipS -= 1
si -= 1
else:
break
while ti >= 0:
if t[ti] == '#':
skipT += 1
ti -= 1
elif skipT > 0:
skipT -= 1
ti -= 1
else:
break
if (si >= 0 and ti >= 0 and s[si] != t[ti]) or (si >= 0) != (ti >= 0):
return False
si -= 1
ti -= 1
return True
# Example usage:
print(backspaceCompare("ab#c", "ad#c")) # True
print(backspaceCompare("ab##", "c#d#")) # True
print(backspaceCompare("a#c", "b")) # Falsepublic class BackspaceStringCompare {
public boolean backspaceCompare(String s, String t) {
int si = s.length() - 1, ti = t.length() - 1;
int skipS = 0, skipT = 0;
while (si >= 0 || ti >= 0) {
while (si >= 0) {
if (s.charAt(si) == '#') { skipS++; si--; }
else if (skipS > 0) { skipS--; si--; }
else break;
}
while (ti >= 0) {
if (t.charAt(ti) == '#') { skipT++; ti--; }
else if (skipT > 0) { skipT--; ti--; }
else break;
}
if ((si >= 0 && ti >= 0 && s.charAt(si) != t.charAt(ti)) || (si >= 0) != (ti >= 0)) {
return false;
}
si--; ti--;
}
return true;
}
public static void main(String[] args) {
BackspaceStringCompare solution = new BackspaceStringCompare();
System.out.println(solution.backspaceCompare("ab#c", "ad#c")); // true
System.out.println(solution.backspaceCompare("ab##", "c#d#")); // true
System.out.println(solution.backspaceCompare("a#c", "b")); // false
}
}#include <iostream>
#include <string>
using namespace std;
bool backspaceCompare(string s, string t) {
int si = s.length() - 1, ti = t.length() - 1;
int skipS = 0, skipT = 0;
while (si >= 0 || ti >= 0) {
while (si >= 0) {
if (s[si] == '#') { skipS++; si--; }
else if (skipS > 0) { skipS--; si--; }
else break;
}
while (ti >= 0) {
if (t[ti] == '#') { skipT++; ti--; }
else if (skipT > 0) { skipT--; ti--; }
else break;
}
if ((si >= 0 && ti >= 0 && s[si] != t[ti]) || ((si >= 0) != (ti >= 0))) {
return false;
}
si--; ti--;
}
return true;
}
int main() {
cout << backspaceCompare("ab#c", "ad#c") << endl; // true
cout << backspaceCompare("ab##", "c#d#") << endl; // true
cout << backspaceCompare("a#c", "b") << endl; // false
return 0;
}function backspaceCompare(s, t) {
let si = s.length - 1, ti = t.length - 1;
let skipS = 0, skipT = 0;
while (si >= 0 || ti >= 0) {
while (si >= 0) {
if (s[si] === '#') { skipS++; si--; }
else if (skipS > 0) { skipS--; si--; }
else break;
}
while (ti >= 0) {
if (t[ti] === '#') { skipT++; ti--; }
else if (skipT > 0) { skipT--; ti--; }
else break;
}
if ((si >= 0 && ti >= 0 && s[si] !== t[ti]) || ((si >= 0) !== (ti >= 0))) {
return false;
}
si--; ti--;
}
return true;
}
// Example usage:
console.log(backspaceCompare("ab#c", "ad#c")); // true
console.log(backspaceCompare("ab##", "c#d#")); // true
console.log(backspaceCompare("a#c", "b")); // false#include <stdbool.h>
#include <stdio.h>
#include <string.h>
bool backspaceCompare(char * s, char * t) {
int si = strlen(s) - 1, ti = strlen(t) - 1;
int skipS = 0, skipT = 0;
while (si >= 0 || ti >= 0) {
while (si >= 0) {
if (s[si] == '#') { skipS++; si--; }
else if (skipS > 0) { skipS--; si--; }
else break;
}
while (ti >= 0) {
if (t[ti] == '#') { skipT++; ti--; }
else if (skipT > 0) { skipT--; ti--; }
else break;
}
if ((si >= 0 && ti >= 0 && s[si] != t[ti]) || ((si >= 0) != (ti >= 0))) {
return false;
}
si--; ti--;
}
return true;
}
int main() {
printf("%d\n", backspaceCompare("ab#c", "ad#c")); // true
printf("%d\n", backspaceCompare("ab##", "c#d#")); // true
printf("%d\n", backspaceCompare("a#c", "b")); // false
return 0;
}using System;
class Program {
static bool BackspaceCompare(string s, string t) {
int si = s.Length - 1, ti = t.Length - 1;
int skipS = 0, skipT = 0;
while (si >= 0 || ti >= 0) {
while (si >= 0) {
if (s[si] == '#') { skipS++; si--; }
else if (skipS > 0) { skipS--; si--; }
else break;
}
while (ti >= 0) {
if (t[ti] == '#') { skipT++; ti--; }
else if (skipT > 0) { skipT--; ti--; }
else break;
}
if ((si >= 0 && ti >= 0 && s[si] != t[ti]) || ((si >= 0) != (ti >= 0))) {
return false;
}
si--; ti--;
}
return true;
}
static void Main(string[] args) {
Console.WriteLine(BackspaceCompare("ab#c", "ad#c")); // true
Console.WriteLine(BackspaceCompare("ab##", "c#d#")); // true
Console.WriteLine(BackspaceCompare("a#c", "b")); // false
}
}In this Python implementation, two pointers are maintained for the two strings, each moving from the end towards the start. Using a counter to track backspaces, the pointers skip over characters as needed to handle backspaces, thereby allowing a direct comparison of the effectively remaining characters.
Time Complexity: O(n + m), due to processing each available character.
Space Complexity: O(1), with only a constant amount of additional memory used.
Approach 3: Default Approach
function backspaceCompare(s: string, t: string): boolean {
let i = s.length - 1;
let j = t.length - 1;
while (i >= 0 || j >= 0) {
let skip = 0;
while (i >= 0) {
if (s[i] === '#') {
skip++;
} else if (skip !== 0) {
skip--;
} else {
break;
}
i--;
}
skip = 0;
while (j >= 0) {
if (t[j] === '#') {
skip++;
} else if (skip !== 0) {
skip--;
} else {
break;
}
j--;
}
if (s[i] !== t[j]) {
return false;
}
i--;
j--;
}
return true;
}func backspaceCompare(s string, t string) bool {
i, j := len(s)-1, len(t)-1
skip1, skip2 := 0, 0
for ; i >= 0 || j >= 0; i, j = i-1, j-1 {
for i >= 0 {
if s[i] == '#' {
skip1++
i--
} else if skip1 > 0 {
skip1--
i--
} else {
break
}
}
for j >= 0 {
if t[j] == '#' {
skip2++
j--
} else if skip2 > 0 {
skip2--
j--
} else {
break
}
}
if i >= 0 && j >= 0 {
if s[i] != t[j] {
return false
}
} else if i >= 0 || j >= 0 {
return false
}
}
return true
}impl Solution {
pub fn backspace_compare(s: String, t: String) -> bool {
let (s, t) = (s.as_bytes(), t.as_bytes());
let (mut i, mut j) = (s.len(), t.len());
while i != 0 || j != 0 {
let mut skip = 0;
while i != 0 {
if s[i - 1] == b'#' {
skip += 1;
} else if skip != 0 {
skip -= 1;
} else {
break;
}
i -= 1;
}
skip = 0;
while j != 0 {
if t[j - 1] == b'#' {
skip += 1;
} else if skip != 0 {
skip -= 1;
} else {
break;
}
j -= 1;
}
if i == 0 && j == 0 {
break;
}
if i == 0 || j == 0 {
return false;
}
if s[i - 1] != t[j - 1] {
return false;
}
i -= 1;
j -= 1;
}
true
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using a Stack to Simulate Typing | Time Complexity: O(n + m), where n and m are the lengths of s and t. |
| Two-Pointer Technique | Time Complexity: O(n + m), due to processing each available character. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack Simulation | O(n) | O(n) | Best for clarity and quick implementation when extra memory is acceptable. |
| Two-Pointer Scan from Right | O(n) | O(1) | Preferred in interviews and memory-constrained scenarios since it avoids building new strings. |
Frequently asked questions
Is Backspace String Compare easy or hard?
Backspace String Compare is classified as an Easy problem. The stack-based simulation is straightforward for beginners, while the two-pointer optimization introduces a useful interview pattern for processing strings in constant space.
Backspace String Compare Python/Java solution
Python and Java implementations typically follow either the stack simulation or the two-pointer approach. The stack solution uses lists or Stack collections to build the final string, while the two-pointer method iterates from the end of the string and compares valid characters without extra storage.
How to solve Backspace String Compare in O(n)?
Traverse both strings from right to left using two pointers. Maintain a skip counter for each string to track pending backspaces. When a '#' appears increase the counter, and when a normal character appears with a positive counter skip it. Compare the next valid characters from both strings until both pointers finish.
What is the best approach for Backspace String Compare?
The optimal approach uses a two-pointer scan from the end of both strings. Each pointer skips characters that are deleted by backspaces using a counter. This method processes each character once, resulting in O(n) time complexity and O(1) extra space, making it more efficient than building new strings.
Is Backspace String Compare asked at Google/Amazon/Meta?
Backspace String Compare is a common interview-style question used by companies such as Amazon, Google, and Meta to test string processing and pointer techniques. It evaluates whether candidates can simulate operations efficiently and optimize space usage.
What data structure is used in Backspace String Compare?
A stack is commonly used to simulate the typing process because it naturally removes the most recently added character when a backspace appears. The optimized solution replaces the stack with two pointers and counters, achieving the same effect with constant extra space.
What is the time complexity of Backspace String Compare?
Both common solutions run in O(n) time where n is the length of the strings. The stack simulation processes every character once while pushing and popping operations. The optimized two-pointer technique also scans each character at most once while skipping deleted characters.