medium Comparing Strings containing Backspaces

Problem Statement

Given two strings containing backspaces (identified by the character ‘#’), check if the two strings are equal.

Example 1:

Input: str1="xy#z", str2="xzz#"
Output: true
Explanation: After applying backspaces the strings become "xz" and "xz" respectively.

Example 2:

Input: str1="xy#z", str2="xyz#"
Output: false
Explanation: After applying backspaces the strings become "xz" and "xy" respectively.

Example 3:

Input: str1="xp#", str2="xyz##"
Output: true
Explanation: After applying backspaces the strings become "x" and "x" respectively.
In "xyz##", the first '#' removes the character 'z' and the second '#' removes the character 'y'.

Example 4:

Input: str1="xywrrmp", str2="xywrrmu#p"
Output: true
Explanation: After applying backspaces the strings become "xywrrmp" and "xywrrmp" respectively.

Constraints:

• 1 <= str1.length, str2.length <= 200
• str1 and str2 only contain lowercase letters and '#' characters.

Solution

To compare the given strings, first, we need to apply the backspaces. An efficient way to do this would be from the end of both the strings. We can have separate pointers, pointing to the last element of the given strings. We can start comparing the characters pointed out by both the pointers to see if the strings are equal. If, at any stage, the character pointed out by any of the pointers is a backspace (’#’), we will skip and apply the backspace until we have a valid character available for comparison.

Here's a detailed walkthrough of the algorithm:

1. In the compare function, two pointers are initialized, index1 and index2, to the last index of str1 and str2, respectively.

2. A while loop is started which continues until both pointers are less than zero, that is, both have traversed their strings completely in a reverse manner.

3. Inside this loop, for each string, the getNextValidCharIndex function is called with the current pointer. This function returns the index of the next valid character in the string (traversing from back to front) by taking into account the backspace characters. i1 and i2 point to the index of the next valid character in the two strings.

4. If both i1 and i2 are less than zero, it means the end of both strings has been reached, and the strings are considered equal.

5. If only one of i1 or i2 is less than zero, it means the end of one string has been reached, but not the other, and the strings are not equal.

6. If the characters at indices i1 and i2 are not the same, the strings are not equal.

7. If none of the above conditions are met, the loop continues to the next valid characters in both strings.

8. The getNextValidCharIndex function accepts a string and an index, and uses a backspace count to keep track of how many backspaces have been encountered. It then loops through the string backwards from the provided index until it encounters a valid character or reaches the beginning of the string.

9. If a backspace character is found, the backspace count is incremented. If a non-backspace character is found and there are any counted backspaces, one backspace is subtracted from the count (to simulate the removal of the previous character), and the loop continues. If a non-backspace character is found and there are no backspaces left to account for, the loop breaks and the index of the valid character is returned.

Algorithm Walkthrough

Input: str1 = "xp#", str2 = "xyz##"

1. Initial pointers: index1 = 2, index2 = 4
2. Process str1 (xp#):
   • index1 = 2 (points to #): increment backspaceCount = 1, move index1 to 1
   • index1 = 1 (points to p): decrement backspaceCount = 0, move index1 to 0
   • index1 = 0 (points to x): valid character found
3. Process str2 (xyz##):
   • index2 = 4 (points to #): increment backspaceCount = 1, move index2 to 3
   • index2 = 3 (points to #): increment backspaceCount = 2, move index2 to 2
   • index2 = 2 (points to z): decrement backspaceCount = 1, move index2 to 1
   • index2 = 1 (points to y): decrement backspaceCount = 0, move index2 to 0
   • index2 = 0 (points to x): valid character found
4. Compare characters:
   • Both characters are x (equal), move index1 to -1 and index2 to -1
5. End of strings: Both pointers are less than zero, strings are equal.

Here is the visual representation of this algorithm for Example 2:

Code

Here is what our algorithm will look like:

Complexity Analysis

Time Complexity

• Outer while loop: The compare() method runs a while loop as long as either index1 or index2 is greater than or equal to 0. This loop processes each character in both strings from right to left. Each iteration of the loop involves finding the next valid character using getNextValidCharIndex().

• getNextValidCharIndex() method: The getNextValidCharIndex() method processes each character of the string at most once. When encountering a # (backspace), it increments the backspaceCount, and when it encounters a valid character after processing backspaces, it returns the index of the valid character.

  • Each character is either counted or skipped exactly once. Therefore, the time complexity of this method is , where N is the length of the string.

Overall time complexity: The two strings are processed independently, so the overall time complexity is , where N and M are the lengths of the two strings str1 and str2, respectively.

Space Complexity

• Constant space usage: The algorithm uses a few integer variables (index1, index2, backspaceCount) to track positions and counts. These variables take up constant space.

• No additional data structures: The algorithm does not use any data structures that scale with the input size, as it works directly on the strings and uses only a fixed amount of space for the pointers and counts.

Overall space complexity: , since only a constant amount of extra space is used.