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.

Try it yourself

Try solving this question here:

After you try — Pattern Transfer

Pattern: REVERSE SCAN WITH SKIP BUDGET (backspace-aware two pointers from the ends).

Simpler alternate: build both cleaned strings with a stack — O(n+m) time and O(n+m) space.

When NOT reverse scan: you need the cleaned string itself (not just equality) → stack; pure forward streaming → stack.

Not sliding window.

Edges

Both empty after apply: "a##" vs "b##" → true; "###" vs "" → true.
Unequal after apply; leading backspaces past start must not crash (skip budget drains).

🎯 STRICT STANDOUT: Why / complexity derivation / pattern+when-not / edges / drills — Comparing Strings containing Backspaces medium

Why this exists (judgment layer)

Equality after edits without building strings is a reverse two-pointer with a skip budget — O(1) extra space vs stack build. Interviewers probe off-by-one when '#' exceeds available characters.

Worked example & complexity derivation

str1="xy#z", str2="xzz#": clean both → "xz" vs "xz" → true
Reverse scan template (per string):
  i from end; skip=0
  while i≥0: if s[i]=='#': skip++; i--
            elif skip>0: skip--; i--
            else: break  # s[i] is next real char
Compare next real chars from both strings until both exhausted
Time O(n+m); space O(1) reverse / O(n+m) stack build
Trace "xyz##": z removed, y removed → "x"

Pattern transfer & when-NOT

Pattern: REVERSE SCAN WITH SKIP BUDGET (backspace two-pointers). Simpler: stack build both cleaned strings. When-NOT reverse: need the cleaned string itself; pure forward streaming API → stack. Not sliding window. Not regex.

Edge cases (hand-run)

"a##" vs "b##" → true (both empty). "###" vs "" → true. Leading '#' past start: skip drains without crash. Unequal residual lengths → false.

Hostile-panel drills (defend the decision)

Q1. Compare "ab##" and "c#d#".
Model answer: Both clean to empty → true.

Q2. Why reverse instead of stack for O(1) space?
Model answer: Backspace deletes the previous kept char; scanning backward applies deletes before emitting the char they affect, so you never store the cleaned string.

Q3. Complexity if both length 200 (constraint max)?
Model answer: O(n+m) ≤ 400 steps; reverse uses O(1) extra pointers/skip counters.

✅ Solution 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:

In the compare function, two pointers are initialized, index1 and index2, to the last index of str1 and str2, respectively.
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.
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.
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.
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.
If the characters at indices i1 and i2 are not the same, the strings are not equal.
If none of the above conditions are met, the loop continues to the next valid characters in both strings.
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.
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##"

Initial pointers: index1 = 2, index2 = 4
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
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
Compare characters:
- Both characters are x (equal), move index1 to -1 and index2 to -1
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:

java

class Solution {

  public boolean compare(String str1, String str2) {
    // use two pointer approach to compare the strings
    int index1 = str1.length() - 1, index2 = str2.length() - 1;
    while (index1 >= 0 || index2 >= 0) {
      int i1 = getNextValidCharIndex(str1, index1);
      int i2 = getNextValidCharIndex(str2, index2);

      if (
        i1 < 0 && i2 < 0
      ) return true; // reached the end of both the strings

      if (
        i1 < 0 || i2 < 0
      ) return false; // reached the end of one of the strings

      if (
        str1.charAt(i1) != str2.charAt(i2)
      ) return false; // check if the characters are equal

      index1 = i1 - 1;
      index2 = i2 - 1;
    }

    return true;
  }

  private static int getNextValidCharIndex(String str, int index) {
    int backspaceCount = 0;
    while (index >= 0) {
      if (
        str.charAt(index) == '#'
      ) backspaceCount++; // found a backspace character
      else if (
        backspaceCount > 0
      ) backspaceCount--; // a non-backspace character
      else break;

      index--; // skip a backspace or a valid character
    }
    return index;
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    System.out.println(sol.compare("xy#z", "xzz#"));
    System.out.println(sol.compare("xy#z", "xyz#"));
    System.out.println(sol.compare("xp#", "xyz##"));
    System.out.println(sol.compare("xywrrmp", "xywrrmu#p"));
  }
}

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.

Pattern Transfer — REVERSE SCAN WITH SKIP BUDGET

Pattern name: reverse two-pointer scan with a backspace skip counter.

Recognition: '#' deletes previous char; compare finals; prefer O(1) auxiliary space.

Template idea: from both ends, getNextValid walks left while tracking backspaceCount: on '#' increment skip; on a letter, if skip>0 consume it, else this is the next real char. Compare the two streams of valid chars.

Stack alternate: for each string, push letters, pop on '#'; compare resulting strings. Example: "ab#c" → stack ['a','c'] → "ac".

Approach	Time	Space	When
Reverse skip scan	Θ(n+m)	O(1)	Equality only; memory tight
Stack build both	Θ(n+m)	Θ(n+m)	Need cleaned string or simpler code

When NOT: need the cleaned string → stack. Not sliding window (no expand/shrink of a contiguous validity window on one array).

Complexity: each index visited at most a constant number of times → Θ(n+m) time, O(1) space for reverse scan.

Edge hand-runs

"a##" vs "b##": both clean to empty → next valid −1 and −1 → true.
"###" vs "" → true.
"a#b" vs "c" → false.
Main: xp# → x; xyz## → x; equal.

Drill: What goes wrong if you scan forward without a stack for equality-only? (You do not know whether a later # will delete the char you just matched.)

🧩 Pattern · Two Pointers

Recognize it: A sorted array where you need a pair/triplet or an in-place partition → walk two indices inward.

▶ Visualize this problem (step it, predict each fork)

⛶ Open this problem debugger in explore mode

🤖 Don't fully get this? Learn it with Claude

Stuck on Comparing Strings containing Backspaces? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Comparing Strings containing Backspaces** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Comparing Strings containing Backspaces** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Comparing Strings containing Backspaces**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Comparing Strings containing Backspaces**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Dutch National Flag Problem Minimum Window Sort →