Backspace String Compare

15 August 2024 — approx 5 min read.

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Problem Statement

LeetCode-844: 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.

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".

Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

Approach

We will discuss two approaches to solve this problem:

Using Stack

The first approach is to use a stack to store the characters of the string. Based on the character encountered, we will either push the character into the stack or pop the top element from the stack:

Iterate over the string and push the characters into the stack.
If we encounter a #, we pop the top element from the stack.
Finally, we compare the two strings formed by the stack.

Here is the java implementation for the stack based approach:

public boolean backspaceCompare(String s, String t) {
    Stack<Character> one = new Stack<>();
    Stack<Character> two = new Stack<>();
    for (char c : s.toCharArray()) {
        if (c == '#' && !one.isEmpty()) {
            one.pop();
        } else if (c != '#') {
            one.push(c);
        }
    }
    for (char c : t.toCharArray()) {
        if (c == '#' && !two.isEmpty()) {
            two.pop();
        } else if (c != '#') {
            two.push(c);
        }
    }
    return one.toString().equals(two.toString());
}

Using Two Pointers

Another approach is to use two pointers to iterate over the strings from the end. We will keep track of the number of backspaces encountered and skip the characters based on the backspace count:

Iterate over the strings from the end and keep track of the number of backspaces encountered.
If we encounter a #, we increment the backspace count.
If we encounter a character, we decrement the backspace count.
If the backspace count is greater than 0, we skip the character.
Finally, we compare the two strings formed by the two pointers.

Here is the java implementation for the above approach:

public boolean backspaceCompare(String s, String t) {
    StringBuilder one = new StringBuilder();
    StringBuilder two = new StringBuilder();
    
    int freq = 0;
    int index = s.length()-1;

    while(index >= 0){
        if(s.charAt(index) == '#'){
            freq++;
        }else if (freq > 0){
            freq--;
        }else{
            one.insert(0, s.charAt(index));
        }
        index--;
    }

    index = t.length()-1;
    freq=0;
    
    while(index >= 0){
        if(t.charAt(index) == '#'){
            freq++;
        }else if (freq > 0){
            freq--;
        }else{
            two.insert(0, t.charAt(index));
        }
        index--;
    }

    return one.toString().equals(two.toString());   
}

Complexity Analysis

The time and space complexity for both the approaches is identical due to similar operations performed in both the approaches.

Using Two Pointers:

Time Complexity: We are iterating over the strings s and t once. Hence, the time complexity is $O(n)$, where $n$ is the combined length of the strings. This can be considered as $O(M+N)$, where $M$ and $N$ are the lengths of individual strings.
Space Complexity: We are using two string builders to store the strings formed by the two pointers. Hence, the space complexity is $O(n)$.

Using Stack:

Time Complexity: Similar to the two pointer approach, the complexity remains $O(n)$.
Space Complexity: Instead of using the StringBuilder instances, we are using stacks in this approach leading to a similar $O(n)$ space complexity.

Follow-up

Can you solve it in $O(n)$ time and O(1) space?

Extending the above approach, we can solve the problem in $O(n)$ time and $O(1)$ space. For this, instead of using the StringBuilder instances, we can directly compare the characters from the two strings. Here is the implementation for the same:

public boolean backspaceCompare(String s, String t) {
    int indexOne = s.length()-1;
    int indexTwo = t.length()-1;
    while(indexOne >=0 || indexTwo >= 0){
        int skipCountOne = 0;
        int skipCountTwo = 0;
        
        // traverse from end until a non #
        // character is found
        while(indexOne >= 0){
            if(s.charAt(indexOne) == '#'){
                skipCountOne++;
                indexOne--;
            }else if(skipCountOne > 0){
                skipCountOne--;
                indexOne--;
            }else{
                break;
            }    
        }
        
        // same as above
        while(indexTwo >= 0){
            if(t.charAt(indexTwo) == '#'){
                skipCountTwo++;
                indexTwo--;
            }else if(skipCountTwo > 0){
                skipCountTwo--;
                indexTwo--;
            }else{
                break;
            }    
        }
        // now at this point, either both the indices
        // point to a non # character which should be same
        // or both are equal to 0
        // if neither, return false
        // case-1: both pointing to non # character
        if(indexOne >= 0 && indexTwo >= 0){
            // it should match
            if(s.charAt(indexOne) != t.charAt(indexTwo)){
                return false;
            }
        }
        // case-2: either of the string is completely 
        // traversed but not other
        else{
            if(indexOne >= 0 || indexTwo >= 0){
                return false;
            }
        }
        indexOne--;
        indexTwo--;
    }
    // finally return true
    return true;
}

This approach is more optimized as it does not use any extra space and solves the problem in $O(n)$ time.

@dsadaily