Backspace String Compare - Solution & Explanation
Problem Statement
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.
The C solution uses an auxiliary array to simulate a stack where each character is pushed unless it is a '#'. If a '#' is encountered and the stack is not empty, the top character is popped (or removed). After processing both strings, we compare the resulting arrays to determine if they are equivalent.
Complexity
Time Complexity: O(n + m), where n and m are the lengths of s and t. Each character is processed once.
Space Complexity: O(n + m) due to the auxiliary arrays used to store the processed results of s and t.
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.
The C implementation of the two-pointer technique uses two pointers to scan the strings from the end to the beginning. We manage two skip counters to skip over unnecessary characters, effectively simulating the result of backspaces without extra space. If the strings differ at any point of effective characters, we return false; otherwise, we return true.
Complexity
Time Complexity: O(n + m), where n and m are the lengths of s and t.
Space Complexity: O(1), since we only use constant space.
Approach 3: Default Approach
Try this approach in the editor →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. Each character is processed once. |
| Two-Pointer Technique | Time Complexity: O(n + m), where n and m are the lengths of s and t. |
| Default Approach | — |
Detailed 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. |
Video Solution
LeetCode Backspace String Compare Solution Explained - Java • Nick White • 32,532 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Backspace String Compare easy or hard?
Backspace String Compare Python/Java solution
How to solve Backspace String Compare in O(n)?
What is the best approach for Backspace String Compare?
Is Backspace String Compare asked at Google/Amazon/Meta?
What data structure is used in Backspace String Compare?
What is the time complexity of Backspace String Compare?
Ready to solve this problem?
Practice Backspace String Compare with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor