Backspace String Compare

📋

Problem

Imagine typing a message on your phone where you often hit backspace. How can you verify if two typed messages are actually the same after considering all backspaces?

Given two strings S and T, return true if they are equal when both are typed into empty text editors. '#' means a backspace character. If a backspace is encountered, it deletes the character before it if any. Return true if the final strings are equal, otherwise false.

1 ≤ length of S, T ≤ 10^5S and T consist of lowercase letters and '#' characters only

Edge cases: Both strings empty → trueStrings with only backspaces → trueOne string empty, other non-empty → false

</>

IDE

def backspaceCompare(S: str, T: str) -> bool:public boolean backspaceCompare(String S, String T)bool backspaceCompare(string S, string T)function backspaceCompare(S, T)

def backspaceCompare(S, T):
    # Write your solution here
    pass

class Solution {
    public boolean backspaceCompare(String S, String T) {
        // Write your solution here
        return false;
    }
}

#include <string>
using namespace std;

bool backspaceCompare(string S, string T) {
    // Write your solution here
    return false;
}

function backspaceCompare(S, T) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: falseIncorrectly simulating backspaces, missing characters that should be removed.✅ Use a stack or two-pointer approach to simulate backspaces correctly before comparing strings.

Wrong: trueReturning true when one string is empty and the other is not after backspace processing.✅ Compare final processed strings' lengths and contents before returning true.

Wrong: trueGreedy removal of characters without proper backspace simulation causing incorrect equality.✅ Simulate backspaces fully using two pointers or stack rather than greedy removal.

Wrong: falseOff-by-one errors removing wrong characters especially at string start.✅ Check index bounds carefully before removing characters during backspace simulation.

Wrong: TLERebuilding strings repeatedly or using inefficient nested loops causing timeouts.✅ Use two-pointer approach from the end to achieve O(n) time complexity.

✓

Test Cases

Try testing your code on empty strings and strings with only backspaces.

Consider tricky cases where backspaces appear at the start or in complex patterns.

Optimize your solution to run in linear time using two pointers from the end.

t1_01basic

Input{"S":"ab#c","T":"ad#c"}

Expectedtrue

⏱ Performance - must finish in 2000ms

Both strings become 'ac' after processing backspaces, so they are equal.

💡 Try simulating the backspace effect by processing each string from left to right.

💡 Use a stack or two pointers to build the final string after applying backspaces.

💡 Compare the final processed strings for equality.

Why it failed: Returned false when strings are actually equal after backspace processing. Fix by correctly simulating backspaces using a stack or two pointers.

✓ Correctly simulates backspaces and compares final strings.

t1_02basic

Input{"S":"ab##","T":"c#d#"}

Expectedtrue

⏱ Performance - must finish in 2000ms

Both strings become empty after processing backspaces, so they are equal.

💡 Check how multiple consecutive backspaces affect the string.

💡 Ensure that backspaces at the start do not cause errors or negative indexing.

💡 Final strings after processing are both empty, so return true.

Why it failed: Returned false when both strings are empty after backspace processing. Fix by handling multiple backspaces correctly and not assuming non-empty strings.

✓ Handles multiple backspaces and empty final strings correctly.

t2_01edge

Input{"S":"","T":""}

Expectedtrue

⏱ Performance - must finish in 2000ms

Both strings are empty, so they are trivially equal.

💡 Consider the case when both input strings are empty.

💡 Empty strings after processing backspaces should return true.

💡 Ensure your code handles empty inputs without errors.

Why it failed: Returned false or error on empty input strings. Fix by adding base case handling for empty strings.

✓ Correctly returns true for empty input strings.

t2_02edge

Input{"S":"######","T":"###"}

Expectedtrue

⏱ Performance - must finish in 2000ms

Both strings contain only backspaces and thus become empty after processing.

💡 Test strings with only backspace characters.

💡 Backspaces on empty strings should not cause errors.

💡 Final processed strings are empty, so return true.

Why it failed: Returned false when strings contain only backspaces. Fix by correctly handling backspaces on empty strings without popping from empty stacks.

✓ Handles strings with only backspaces correctly.

t2_03edge

Input{"S":"","T":"a"}

Expectedfalse

⏱ Performance - must finish in 2000ms

One string is empty, the other is not, so they cannot be equal.

💡 Check cases where one string is empty and the other is not.

💡 After processing backspaces, compare final string lengths.

💡 If lengths differ, return false immediately.

Why it failed: Returned true when one string is empty and the other is not. Fix by comparing final string lengths after processing.

✓ Correctly returns false when one string is empty and the other is not.

t3_01corner

Input{"S":"a#c","T":"b"}

Expectedfalse

⏱ Performance - must finish in 2000ms

After processing, S becomes 'c' and T is 'b', which are not equal.

💡 Beware of greedy approaches that assume backspaces always remove the previous character.

💡 Simulate backspaces carefully to avoid skipping characters incorrectly.

💡 Check final strings character by character after processing.

Why it failed: Returned true incorrectly due to greedy removal of characters without proper simulation. Fix by simulating backspaces fully rather than removing characters greedily.

✓ Correctly simulates backspaces and compares final strings.

t3_02corner

Input{"S":"bxj##tw","T":"bxo#j##tw"}

Expectedtrue

⏱ Performance - must finish in 2000ms

Both strings become 'btw' after processing backspaces.

💡 Check that backspaces remove the correct preceding characters even with complex patterns.

💡 Use two pointers from the end to simulate backspaces on the fly.

💡 Compare characters only after accounting for all backspaces.

Why it failed: Returned false due to incorrect handling of multiple backspaces in sequence. Fix by correctly counting backspaces and skipping characters accordingly.

✓ Handles complex backspace patterns correctly.

t3_03corner

Input{"S":"nzp#o#g","T":"b#nzp#o#g"}

Expectedtrue

⏱ Performance - must finish in 2000ms

Both strings become 'nzog' after processing backspaces.

💡 Beware of off-by-one errors when processing backspaces at string start.

💡 Ensure backspaces do not remove characters beyond string start.

💡 Simulate backspaces carefully to handle edge positions.

Why it failed: Returned false due to off-by-one error removing wrong characters. Fix by checking index bounds before removing characters.

✓ Correctly handles backspaces at string start.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input size n=100000 tests O(n) time complexity solutions to complete within 2 seconds.

💡 Aim for O(n) time complexity by simulating backspaces with two pointers.

💡 Avoid building full strings with stacks to save space and time.

💡 Process strings from end to start to skip characters efficiently.

Why it failed: TLE due to O(n^2) or exponential complexity from rebuilding strings repeatedly. Fix by using two-pointer approach with O(n) time.

✓ Solution runs in O(n) time and passes performance test.

Practice

1. Consider the following code snippet implementing the 3Sum Closest algorithm. What is the returned value when the input is nums = [-1, 2, 1, -4] and target = 1?

def threeSumClosest(nums, target):
    nums.sort()
    n = len(nums)
    closest_sum = nums[0] + nums[1] + nums[2]
    for i in range(n - 2):
        left, right = i + 1, n - 1
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            if current_sum == target:
                return current_sum
            if abs(current_sum - target) < abs(closest_sum - target):
                closest_sum = current_sum
            if current_sum < target:
                left += 1
            else:
                right -= 1
    return closest_sum

print(threeSumClosest([-1, 2, 1, -4], 1))

easy

A. 1

B. 4

C. -1

D. 2

Solution

1. Step 1: Sort the array

   Sorted nums = [-4, -1, 1, 2]

2. Step 2: Trace iterations

   i=0: left=1, right=3 current_sum = -4 + (-1) + 2 = -3 (closest_sum init = -4+-1+1 = -4) Update closest_sum to -3 current_sum < target(1), left++ -> left=2 current_sum = -4 + 1 + 2 = -1 Update closest_sum to -1 current_sum < target, left++ -> left=3 (loop ends) i=1: left=2, right=3 current_sum = -1 + 1 + 2 = 2 abs(2-1)=1 < abs(-1-1)=2, update closest_sum=2 current_sum > target, right-- -> right=2 (loop ends) Return closest_sum = 2

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Output matches expected closest sum 2 [OK]

Hint: Sorting and pointer moves yield closest sum 2 [OK]

Common Mistakes:

• Returning initial sum without updates
• Off-by-one pointer increments
• Confusing current_sum with closest_sum

2. What is the time and space complexity of the optimal two-pointer overwrite approach for moving zeroes to the end of an array of length n?

medium

A. Time: O(n), Space: O(1) because it scans array twice but no extra space

B. Time: O(n^2), Space: O(1) due to nested loops

C. Time: O(n), Space: O(n) because it uses an auxiliary array implicitly

D. Time: O(n log n), Space: O(1) due to sorting involved

Solution

1. Step 1: Identify loops and operations

   The algorithm scans the array twice sequentially: once to overwrite non-zero elements, once to fill zeroes.

2. Step 2: Analyze time and space

   Each loop is O(n), total O(n). No extra arrays or recursion used, so space is O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two linear passes, constant extra space [OK]

Hint: Two linear scans, no nested loops or extra arrays [OK]

Common Mistakes:

• Mistaking two loops as nested (O(n^2))
• Assuming extra space due to overwriting
• Confusing with sorting complexity

3. The following code attempts to move zeroes to the end of the array in-place:

def moveZeroes(nums):
    lastNonZeroFoundAt = 0
    for num in nums:
        if num != 0:
            nums[lastNonZeroFoundAt] = num
            lastNonZeroFoundAt += 1
    # Bug introduced here
    for i in range(lastNonZeroFoundAt, len(nums)):
        nums[i] = nums[i]

What is the bug in this code?

medium

A. The variable lastNonZeroFoundAt is incremented incorrectly.

B. The first loop does not correctly identify non-zero elements.

C. The second loop does not fill zeroes after lastNonZeroFoundAt, leaving old values intact.

D. The assignment inside the first loop overwrites zeroes incorrectly.

Solution

1. Step 1: Analyze second loop behavior

   The second loop assigns nums[i] = nums[i], which does nothing and fails to fill zeroes.

2. Step 2: Identify correct fix

   It should assign nums[i] = 0 to move zeroes to the end properly.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Zeroes remain unfilled, causing incorrect output [OK]

Hint: Second loop must fill zeroes, not copy existing values [OK]

Common Mistakes:

• Forgetting to fill zeroes after moving non-zero elements
• Misunderstanding loop purpose

4. Suppose the problem changes so that elements can be reused multiple times in triplets (i.e., indices can repeat). Which modification to the two-pointer approach correctly counts the number of triplets with sum less than target?

hard

A. Keep the same two-pointer approach but allow left and right pointers to be equal and count accordingly.

B. Use three nested loops to consider all triplets with possible repeated indices.

C. Sort the array and for each i, use two pointers starting at i to allow reuse, adjusting counting logic accordingly.

D. Sort the array and for each i, use a single pointer to count pairs with sum less than target minus nums[i], allowing reuse.

Solution

1. Step 1: Understand reuse of elements

   Allowing repeated indices means pairs can include the same element multiple times, so two-pointer approach must adapt.

2. Step 2: Adjust approach for reuse

   Using a single pointer to count pairs with sum less than target - nums[i] allows counting with reuse, since two pointers crossing is no longer valid.

3. Step 3: Why other options fail

   Allowing left == right breaks two-pointer logic (A). Three nested loops (B) is correct but inefficient. Starting two pointers at i (C) is incorrect because it counts invalid pairs.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Single pointer counting with reuse is correct and efficient [OK]

Hint: Reuse requires counting pairs with single pointer or adjusted logic [OK]

Common Mistakes:

• Allowing pointers to cross causing invalid counts
• Using naive triple loops ignoring efficiency
• Starting two pointers incorrectly leading to missed counts

5. Suppose the array is not sorted and you want to remove duplicates in-place with O(1) extra space. Which modification to the two-pointer approach is correct?

hard

A. Scan the array multiple times with nested loops to remove duplicates.

B. Use two pointers without sorting, comparing elements directly to remove duplicates.

C. Use a hash set to track duplicates and overwrite duplicates in-place.

D. Sort the array first, then apply the two-pointer approach.

Solution

1. Step 1: Understand constraints

   Two-pointer approach relies on sorted array to detect duplicates in one pass.

2. Step 2: Identify correct modification

   Sorting first ensures duplicates are adjacent, enabling two-pointer removal in O(n log n) time and O(1) space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting enables two-pointer approach on unsorted input [OK]

Hint: Two-pointer requires sorted array; sort first if unsorted [OK]

Common Mistakes:

• Trying two-pointer without sorting
• Using extra space violating constraints