844. Backspace String Compare

EasyStackTwo PointersStringSimulation
Leetcode Link

Problem Description

This problem involves comparing two strings to determine if they are the same after processing all backspace operations. In the strings, each # character represents a backspace operation. The backspace operation removes the character immediately before it, or does nothing if there is no character to remove (i.e., at the beginning of the string). The goal is to return true if, after applying all backspace operations, the two strings are equal, otherwise return false.

Let's consider an example. If we have the string "ab#c", processing the backspace operations would result in the string "ac", since the # removes the preceding b. On the other hand, "a#d#" after processing would become "", as both characters are removed by backspaces.

The challenge is to do this comparison efficiently without actually reconstructing the strings after applying the backspace operations.

Intuition

The solution is based on traversing both strings from the end to the start, simulating the backspace operations as we go. This way, we can compare characters that would appear on screen without building the resultant strings.

Here's how we can think about the problem:

  1. We start by pointing at the last characters of both s and t.
  2. We move backwards through each string. Whenever we encounter a #, it signifies that we need to skip the next non-# character since it is "backspaced." We keep a count of how many characters to skip.
  3. Whenever we are not supposed to skip characters (the skip count is zero), we compare the characters at the current position in both s and t. If they are different, we return false.
  4. If we reach the beginning of one string but not the other (meaning one string has more characters that would appear on screen than the other), the strings are not equal, and we return false.
  5. If both pointers reach the beginning without finding any mismatch, the strings are the same after processing backspaces, and we return true.

In summary, the intuition is to iterate from the end to the beginning of the strings while keeping track of backspaces, hence ensuring that only characters that would appear on the screen are compared.

Learn more about Stack and Two Pointers patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Solution Approach

The implementation uses a two-pointer approach. This means we have a pointer for each string (s and t), starting from the end of the strings and moving towards the beginning. The variables i and j serve as pointers for strings s and t, respectively.

Here's a step-by-step explanation of the solution:

  1. Initialize pointers i and j to the last indices of s and t respectively.
  2. Use two additional variables skip1 and skip2 to keep track of the number of backspaces (#) encountered in each string. These variables indicate how many characters we should skip over as we move backwards.
  3. Use a while loop to walk through both strings concurrently until both pointers reach the beginning of their respective strings.
    • For each string s and t, if the current character is #, increment the respective skip variable (skip1 for s and skip2 for t) and move the pointer one step back.
    • If the current character is not # and the skip variable is greater than zero, decrement the skip variable and move the pointer one step back without comparing any characters. This simulates the backspace operation.
    • If the current character is not # and the skip variable is zero, this is a character that would actually appear on screen, and we can pause this step to compare it against the character in the other string.
  4. Compare the characters from each string that are at the current positions:
    • If both pointers are within the bounds of their strings and the characters are different, return false.
    • If one pointer is within the bounds of its string and the other is not, return false, because one string has more visible characters than the other.
  5. Decrement both pointers i and j and return to step 3, continuing this process.
  6. Once both strings have been fully processed, if no mismatches were found, the function returns true.

The beauty of this algorithm is that it simulates the text editing process without needing extra space to store the resultant strings after backspace operations, making it an efficient solution in terms of space complexity, which is O(1). The time complexity of the algorithm is O(N + M), where N and M are the lengths of strings s and t respectively, as each character in both strings is visited at most twice.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Example Walkthrough

Let's use the solution approach to compare two example strings, s = "ab##" and t = "c#d#" to determine if they are equal after processing backspace operations.

We'll walk through each step of the solution:

  1. Initialize pointers i to index 3 (last index of s) and j to index 3 (last index of t).
  2. Initialize skip variables skip1 and skip2 to 0.

Step-by-step processing:

  • Iteration 1:

    • s[i] is # so we increment skip1 to 1 and decrement i to 2.
    • t[j] is # so we increment skip2 to 1 and decrement j to 2.

  • Iteration 2:

    • s[i] is # again, so now skip1 becomes 2 and i is decremented to 1.
    • t[j] is d, but skip2 is 1, so we decrement skip2 to 0 and j to 1 without comparing the characters.

  • Iteration 3:

    • s[i] is b, but skip1 is 2, so we decrement skip1 to 1 and i to 0.
    • t[j] is c, and skip2 is 0, so we should compare t[j] with s[i]. However, we notice skip1 is still greater than 0, so we decrement skip1 to 0 and i is now -1 (out of bounds).

  • Iteration 4:

    • i is out of bounds, so we can't process s anymore.
    • t[j] is c and skip2 is 0, so c would be a character that should appear on the screen. Since i is out of bounds, we compare an out-of-bounds s[i] with t[j] which has a visible character 'c'.

  • Conclusion:

    • Since i is out of bounds and j points to a visible character, the strings are not the same after processing the backspace operations. We don't need to check the remaining characters in s since we know at this point that the visible characters are different.

Hence, the function would return false. This example demonstrates that string s becomes empty after applying all backspace operations whereas string t results in the character 'c', making the strings unequal.

Solution Implementation

1class Solution:
2    def backspace_compare(self, string1: str, string2: str) -> bool:
3        # Initialize pointers for both strings starting from the end
4        index1, index2 = len(string1) - 1, len(string2) - 1
5        # Initialize counters for skip characters ('#')
6        skip_count1, skip_count2 = 0, 0
7
8        # Compare characters in the strings from the end
9        while index1 >= 0 or index2 >= 0:
10            # Find the position of next valid character in string1
11            while index1 >= 0:
12                if string1[index1] == '#':
13                    skip_count1 += 1
14                    index1 -= 1
15                elif skip_count1 > 0:
16                    skip_count1 -= 1
17                    index1 -= 1
18                else:
19                    break  # Found a valid character
20
21            # Find the position of next valid character in string2
22            while index2 >= 0:
23                if string2[index2] == '#':
24                    skip_count2 += 1
25                    index2 -= 1
26                elif skip_count2 > 0:
27                    skip_count2 -= 1
28                    index2 -= 1
29                else:
30                    break  # Found a valid character
31
32            # If both strings have valid characters to compare
33            if index1 >= 0 and index2 >= 0:
34                if string1[index1] != string2[index2]:
35                    # Characters do not match
36                    return False
37            # If one index is negative, it means one string has more characters left after processing backspaces
38            elif index1 >= 0 or index2 >= 0:
39                return False
40
41            # Move to the next character
42            index1, index2 = index1 - 1, index2 - 1
43
44        # If all characters matched, return True
45        return True
46
1class Solution {
2    public boolean backspaceCompare(String s, String t) {
3        // Initialize two pointers for iterating through the strings in reverse.
4        int pointerS = s.length() - 1, pointerT = t.length() - 1;
5        // Variables to keep track of the number of backspaces found.
6        int skipS = 0, skipT = 0;
7
8        // Continue comparing characters until both pointers go beyond the start of the string.
9        while (pointerS >= 0 || pointerT >= 0) {
10            // Process backspaces in string s.
11            while (pointerS >= 0) {
12                if (s.charAt(pointerS) == '#') {
13                    skipS++; // We found a backspace character.
14                    pointerS--; // Move one character back.
15                } else if (skipS > 0) {
16                    skipS--; // Reduce the backspace count.
17                    pointerS--; // Skip over this character.
18                } else {
19                    break; // Found a character to compare.
20                }
21            }
22            // Process backspaces in string t.
23            while (pointerT >= 0) {
24                if (t.charAt(pointerT) == '#') {
25                    skipT++; // We found a backspace character.
26                    pointerT--; // Move one character back.
27                } else if (skipT > 0) {
28                    skipT--; // Reduce the backspace count.
29                    pointerT--; // Skip over this character.
30                } else {
31                    break; // Found a character to compare.
32                }
33            }
34          
35            // Compare the characters of both strings.
36            if (pointerS >= 0 && pointerT >= 0) {
37                // If characters do not match, return false.
38                if (s.charAt(pointerS) != t.charAt(pointerT)) {
39                    return false;
40                }
41            } else if (pointerS >= 0 || pointerT >= 0) {
42                // If one pointer has reached the start but the other has not, they do not match.
43                return false;
44            }
45            // Move to the next characters to compare.
46            pointerS--;
47            pointerT--;
48        }
49        // All characters match considering the backspace characters.
50        return true;
51    }
52}
53
1class Solution {
2public:
3    // Function to compare two strings considering '#' as a backspace character.
4    bool backspaceCompare(string s, string t) {
5        // Initialize two pointers for the end of the strings.
6        int sIndex = s.size() - 1, tIndex = t.size() - 1;
7        // Initialize counters for the number of backspaces in s and t.
8        int sSkip = 0, tSkip = 0;
9
10        // While there are characters to compare in either string.
11        while (sIndex >= 0 || tIndex >= 0) {
12            // Find position of next possible character in s.
13            while (sIndex >= 0) {
14                if (s[sIndex] == '#') { // If a backspace char found, increment the skip counter.
15                    ++sSkip;
16                    --sIndex;
17                } else if (sSkip > 0) { // If we have backspaces to apply, decrement the counter and index.
18                    --sSkip;
19                    --sIndex;
20                } else {
21                    break; // Found a valid character to compare.
22                }
23            }
24
25            // Find position of next possible character in t.
26            while (tIndex >= 0) {
27                if (t[tIndex] == '#') { // If a backspace char found, increment the skip counter.
28                    ++tSkip;
29                    --tIndex;
30                } else if (tSkip > 0) { // If we have backspaces to apply, decrement the counter and index.
31                    --tSkip;
32                    --tIndex;
33                } else {
34                    break; // Found a valid character to compare.
35                }
36            }
37
38            // If both current indices are valid, compare the characters from s and t.
39            if (sIndex >= 0 && tIndex >= 0) {
40                // If the characters are different, return false.
41                if (s[sIndex] != t[tIndex]) return false;
42            } else if (sIndex >= 0 || tIndex >= 0) {
43                // If one string has ended, but the other has not, they are not the same.
44                return false;
45            }
46
47            // Move to the next character in each string.
48            --sIndex;
49            --tIndex;
50        }
51
52        // All compared characters are equal, return true.
53        return true;
54    }
55};
56
1function backspaceCompare(S: string, T: string): boolean {
2    // Initialize two pointers, starting from the end of each string.
3    let pointerS = S.length - 1;
4    let pointerT = T.length - 1;
5
6    // Continue comparing as long as there's a character in either string.
7    while (pointerS >= 0 || pointerT >= 0) {
8        let skipS = 0; // To count the backspaces in S.
9        // Processing backspaces for S.
10        while (pointerS >= 0) {
11            if (S[pointerS] === '#') {
12                skipS++; // Found a backspace; increase count.
13            } else if (skipS > 0) {
14                skipS--; // Skip the character due to a previous backspace.
15            } else {
16                break; // Found a valid character to compare.
17            }
18            pointerS--; // Move backwards in string S.
19        }
20
21        let skipT = 0; // To count the backspaces in T.
22        // Processing backspaces for T.
23        while (pointerT >= 0) {
24            if (T[pointerT] === '#') {
25                skipT++; // Found a backspace; increase count.
26            } else if (skipT > 0) {
27                skipT--; // Skip the character due to a previous backspace.
28            } else {
29                break; // Found a valid character to compare.
30            }
31            pointerT--; // Move backwards in string T.
32        }
33
34        // Compare the characters of S and T at the pointers.
35        if (pointerS >= 0 && pointerT >= 0 && S[pointerS] !== T[pointerT]) {
36            return false; // Characters do not match.
37        }
38
39        // If one string is at the end, make sure the other is too.
40        if ((pointerS >= 0) !== (pointerT >= 0)) {
41            return false; // One string ended prematurely.
42        }
43
44        // Move to the next valid character in the string.
45        pointerS--;
46        pointerT--;
47    }
48
49    // All compared characters matched.
50    return true;
51}
52
Not Sure What to Study? Take the 2-min Quiz：

How many times is a tree node visited in a depth first search?

Time and Space Complexity

The time complexity of the given code is O(N + M), where N is the length of string s and M is the length of string t. This is because in the worst case, the algorithm may have to iterate through all the characters in both strings once. The backspace character (#) processing only increases the number of iterations by a constant factor, not the overall complexity.

The space complexity of the code is O(1). This is because the space required for the variables i, j, skip1, and skip2 does not depend on the size of the input strings, making it constant space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers iframe width 560 height 315 src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe Two pointers is a common interview technique

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫