Backspace String Compare

Easy

#0798Time: O(N + M), where N and M are the lengths of strings `s` and `t` respectively. We iterate through each string once to build the final strings, and then compare them.Space: O(N + M). In the worst case (no backspaces), the `StringBuilder`s will store all characters of the original strings, where N and M are the lengths of s and t.10 companies

Patterns

Two Pointers

Data structures

String Stack

Companies

Agoda Chewy IBM Tinkoff

Prompt

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 <= 200
s and t only contain lowercase letters and '#' characters.

Follow up: Can you solve it in O(n) time and O(1) space?

Approaches

2 approaches with complexity analysis and trade-offs.

This approach simulates the process of typing the characters of each string into a text editor. We can build the final resulting strings for both s and t after processing all the backspace characters. Finally, we compare the two built strings to see if they are identical.

Algorithm

Create a helper function build(String str).
Inside build, initialize an empty StringBuilder.
Iterate through each character of the input string str.
If the character is not '#', append it to the StringBuilder.
If the character is '#' and the StringBuilder is not empty, remove its last character.
After the loop, return the string representation of the StringBuilder.
In the main function, call build(s) and build(t).
Compare the two resulting strings for equality and return the result.

Walkthrough

We can write a helper function that takes a string and returns its final version after applying backspaces. This function iterates through the input string and uses a StringBuilder (or a stack) to construct the result.

When a non-backspace character is encountered, it's appended to the StringBuilder.
When a backspace character ('#') is found, if the StringBuilder is not empty, the last character is deleted.
After processing both s and t with this helper function, we get two final strings. The problem then reduces to a simple string comparison.

1class Solution {2    public boolean backspaceCompare(String s, String t) {3        return build(s).equals(build(t));4    }5 6    private String build(String str) {7        StringBuilder sb = new StringBuilder();8        for (char c : str.toCharArray()) {9            if (c != '#') {10                sb.append(c);11            } else if (sb.length() > 0) {12                sb.deleteCharAt(sb.length() - 1);13            }14        }15        return sb.toString();16    }17}

Complexity

Time

O(N + M), where N and M are the lengths of strings `s` and `t` respectively. We iterate through each string once to build the final strings, and then compare them.

Space

O(N + M). In the worst case (no backspaces), the `StringBuilder`s will store all characters of the original strings, where N and M are the lengths of s and t.

Trade-offs

Pros

Conceptually simple and easy to implement.
The logic directly follows the problem description.

Cons

Requires extra space proportional to the input string lengths, which does not meet the follow-up constraint of O(1) space.

To solve the problem in O(1) space, we can avoid creating new strings. Instead, we can compare the characters of s and t one by one, from right to left. Iterating from the end is beneficial because a backspace character '#' tells us to skip the next valid character to its left. This approach allows us to find the next character that would appear in the final string without actually building it.

Algorithm

Initialize two pointers, i to s.length() - 1 and j to t.length() - 1.
Initialize two skip counters, skipS and skipT, to 0.
Loop while i >= 0 or j >= 0.
Inside the loop, find the next valid character for s: use a nested while loop that moves i left. If s.charAt(i) is '#', increment skipS. If s.charAt(i) is a letter and skipS > 0, decrement skipS. Break when a valid character is found (letter with skipS == 0).
Similarly, find the next valid character for t using pointer j and counter skipT.
After finding the valid characters (or reaching the beginning of a string), compare their states:
If both i and j are valid indices and s.charAt(i) is not equal to t.charAt(j), return false.
If one pointer is valid (>= 0) and the other is not, it means the effective lengths are different. Return false.
Decrement both i and j to proceed to the next characters.
If the main loop completes, it means the strings are equivalent. Return true.

Walkthrough

We use two pointers, i and j, initialized to the end of strings s and t respectively. We iterate backwards as long as there are characters to process in either string. In each step of the main loop, we find the next valid character in s and t. A valid character is one that is not a backspace and is not skipped by a backspace.

To find the next valid character in s (similarly for t), we use an inner loop. We also maintain a skip counter. If we see a '#', we increment skip and move the pointer left. If we see a non-'#' character while skip > 0, we decrement skip and move the pointer left (as this character is 'deleted'). We stop when we find a non-'#' character with skip == 0, or when the pointer goes out of bounds.
After finding the next valid characters from both strings (or determining that one string is exhausted), we compare them.
If the characters are different, the strings are not equivalent, and we return false.
If one string has a valid character while the other is exhausted, they are not equivalent, so we return false.
If both are exhausted simultaneously or the characters match, we continue by moving both pointers to the left.
If the entire loop completes, it means the strings are equivalent, and we return true.

1class Solution {2    public boolean backspaceCompare(String s, String t) {3        int i = s.length() - 1;4        int j = t.length() - 1;5        int skipS = 0;6        int skipT = 0;7 8        while (i >= 0 || j >= 0) {9            // Find next valid character in s10            while (i >= 0) {11                if (s.charAt(i) == '#') {12                    skipS++;13                    i--;14                } else if (skipS > 0) {15                    skipS--;16                    i--;17                } else {18                    break;19                }20            }21 22            // Find next valid character in t23            while (j >= 0) {24                if (t.charAt(j) == '#') {25                    skipT++;26                    j--;27                } else if (skipT > 0) {28                    skipT--;29                    j--;30                } else {31                    break;32                }33            }34 35            // If two actual characters are different36            if (i >= 0 && j >= 0 && s.charAt(i) != t.charAt(j)) {37                return false;38            }39            40            // If one string is empty while the other is not41            if ((i >= 0) != (j >= 0)) {42                return false;43            }44 45            i--;46            j--;47        }48 49        return true;50    }51}

Complexity

Time

O(N + M), where N and M are the lengths of `s` and `t`. Although there are nested loops, each character of `s` and `t` is visited at most twice, so the complexity is linear.

Space

O(1). We only use a constant amount of extra space for pointers and counters, regardless of the input size.

Trade-offs

Pros

Highly efficient in terms of space, meeting the O(1) space complexity follow-up.
Time complexity is also optimal at O(N + M).

Cons

The logic is more complex than the build-string approach, with nested loops and multiple conditions to manage.
Can be slightly harder to debug if implemented incorrectly.

Solutions

Solution

1class Solution {2public3  boolean backspaceCompare(String s, String t) {4    int i = s.length() - 1, j = t.length() - 1;5    int skip1 = 0, skip2 = 0;6    for (; i >= 0 || j >= 0; --i, --j) {7      while (i >= 0) {8        if (s.charAt(i) == '#') {9          ++skip1;10          --i;11        } else if (skip1 > 0) {12          --skip1;13          --i;14        } else {15          break;16        }17      }18      while (j >= 0) {19        if (t.charAt(j) == '#') {20          ++skip2;21          --j;22        } else if (skip2 > 0) {23          --skip2;24          --j;25        } else {26          break;27        }28      }29      if (i >= 0 && j >= 0) {30        if (s.charAt(i) != t.charAt(j)) {31          return false;32        }33      } else if (i >= 0 || j >= 0) {34        return false;35      }36    }37    return true;38  }39}

1class Solution {2public:3  bool backspaceCompare(string s, string t) {4    int i = s.size() - 1, j = t.size() - 1;5    int skip1 = 0, skip2 = 0;6    for (; i >= 0 || j >= 0; --i, --j) {7      while (i >= 0) {8        if (s[i] == '#') {9          ++skip1;10          --i;11        } else if (skip1) {12          --skip1;13          --i;14        } else15          break;16      }17      while (j >= 0) {18        if (t[j] == '#') {19          ++skip2;20          --j;21        } else if (skip2) {22          --skip2;23          --j;24        } else25          break;26      }27      if (i >= 0 && j >= 0) {28        if (s[i] != t[j])29          return false;30      } else if (i >= 0 || j >= 0)31        return false;32    }33    return true;34  }35};

1class Solution:2    def backspaceCompare(self, s: str, t: str) -> bool: i, j, skip1, skip2 = len(s) - 1, len(t) - 1, 0, 0 while i >= 0 or j >= 0: while i >= 0: if s[i] == '#': skip1 += 1 i -= 1 elif skip1: skip1 -= 1 i -= 1 else: break while j >= 0: if t[j] == '#': skip2 += 1 j -= 1 elif skip2: skip2 -= 1 j -= 1 else: break if i >= 0 and j >= 0: if s[i] != t[j]: return False elif i >= 0 or j >= 0: return False i, j = i - 1, j - 1 return True

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem