Backspace String Compare

▶

Steps

setup

Initialize S array and pointers

Convert string S to a character array and initialize write pointer at 0 to start rebuilding.

💡 We need a mutable array and a write pointer to simulate backspace in-place.

Line:

arr = list(S)
write = 0

💡 Starting with write=0 means no characters have been processed yet.

fill_cells

Read first character 'a' in S

Read pointer moves to index 0, character 'a' is not '#', so write 'a' at write=0 and increment write.

💡 Non-backspace characters are copied forward to build the final string.

Line:

if arr[read] != '#':
    arr[write] = arr[read]
    write += 1

💡 Write pointer advances only when adding valid characters.

fill_cells

Read second character 'b' in S

Read pointer moves to index 1, character 'b' is not '#', write 'b' at write=1 and increment write.

💡 Continuing to copy valid characters forward.

Line:

if arr[read] != '#':
    arr[write] = arr[read]
    write += 1

💡 Write pointer now at 2, showing two valid characters processed.

shrink

Read third character '#' in S (backspace)

Read pointer moves to index 2, character is '#', so decrement write pointer to remove last character if possible.

💡 Backspace removes the last valid character by moving write pointer back.

Line:

elif write > 0:
    write -= 1

💡 Write pointer moves from 2 to 1, effectively deleting 'b'.

fill_cells

Read fourth character 'c' in S

Read pointer moves to index 3, character 'c' is not '#', write 'c' at write=1 and increment write.

💡 Add new valid character after backspace effect.

Line:

if arr[read] != '#':
    arr[write] = arr[read]
    write += 1

💡 Rebuilt string is now 'ac'.

reconstruct

Finish processing S and build string

Join characters from index 0 to write=2 to form rebuilt string 'ac' for S.

💡 Final rebuilt string after applying backspaces is ready for comparison.

Line:

return ''.join(arr[:write])

💡 S rebuild complete: 'ac'.

setup

Initialize T array and pointers

Convert string T to a character array and initialize write pointer at 0.

💡 Prepare to rebuild T similarly to S.

Line:

arr = list(T)
write = 0

💡 Ready to process T with same logic.

fill_cells

Read first character 'a' in T

Read pointer moves to index 0, character 'a' is not '#', write 'a' at write=0 and increment write.

💡 Copy valid character forward.

Line:

if arr[read] != '#':
    arr[write] = arr[read]
    write += 1

💡 Write pointer now at 1.

fill_cells

Read second character 'd' in T

Read pointer moves to index 1, character 'd' is not '#', write 'd' at write=1 and increment write.

💡 Add next valid character.

Line:

if arr[read] != '#':
    arr[write] = arr[read]
    write += 1

💡 Write pointer now at 2.

shrink

Read third character '#' in T (backspace)

Read pointer moves to index 2, character is '#', decrement write pointer to remove last character if possible.

💡 Backspace removes last valid character by moving write pointer back.

Line:

elif write > 0:
    write -= 1

💡 Write pointer moves from 2 to 1, removing 'd'.

fill_cells

Read fourth character 'c' in T

Read pointer moves to index 3, character 'c' is not '#', write 'c' at write=1 and increment write.

💡 Add valid character after backspace effect.

Line:

if arr[read] != '#':
    arr[write] = arr[read]
    write += 1

💡 Rebuilt string is now 'ac'.

reconstruct

Finish processing T and build string

Join characters from index 0 to write=2 to form rebuilt string 'ac' for T.

💡 Final rebuilt string after applying backspaces is ready for comparison.

Line:

return ''.join(arr[:write])

💡 T rebuild complete: 'ac'.

compare

Compare rebuilt strings

Compare rebuilt strings from S and T, both are 'ac', so they are equal.

💡 Final equality check determines the answer.

Line:

return build(list(S)) == build(list(T))

💡 Backspace processing yields identical strings.

def backspaceCompare(S: str, T: str) -> bool:
    def build(arr):
        write = 0  # STEP 1,7
        for read in range(len(arr)):
            if arr[read] != '#':  # STEP 2,3,5,8,9,11
                arr[write] = arr[read]
                write += 1
            elif write > 0:  # STEP 4,10
                write -= 1
        return ''.join(arr[:write])  # STEP 6,12

    return build(list(S)) == build(list(T))  # STEP 13

if __name__ == '__main__':
    print(backspaceCompare("ab#c", "ad#c"))  # True

📊

Backspace String Compare - Watch the Algorithm Execute, Step by Step

Watching each pointer move and overwrite operation reveals how backspaces remove characters without extra space, clarifying the algorithm's efficiency.

setup

write

a

0

b

1

#

2

c

3

Result: ""

move_right

read

a

0

write

b

1

#

2

c

3

Result: "a"

move_right

a

0

read

b

1

write

#

2

c

3

Result: "ab"

move_left

a

0

write

b

1

read

#

2

c

3

Result: "a"

move_right

a

0

c

1

write

#

2

read

c

3

Result: "ac"

record

a

0

c

1

write

#

2

read

c

3

Result: "ac"

setup

write

a

0

d

1

#

2

c

3

Result: ""

move_right

read

a

0

write

d

1

#

2

c

3

Result: "a"

move_right

a

0

read

d

1

write

#

2

c

3

Result: "ad"

move_left

a

0

write

d

1

read

#

2

c

3

Result: "a"

move_right

a

0

c

1

write

#

2

read

c

3

Result: "ac"

record

a

0

c

1

write

#

2

read

c

3

Result: "ac"

compare

a

0

c

1

Result: true

Key Takeaways

✓ The write pointer simulates backspace by moving backward, effectively deleting characters in-place.

This is hard to see from code alone because the write pointer movement is subtle and not explicit deletion.

✓ Processing strings forward with two pointers avoids extra space and multiple passes.

Visualizing pointer movement clarifies how the algorithm is efficient and in-place.

✓ Final comparison is done only on the rebuilt prefixes up to the write pointer, not the entire original strings.

This shows why the algorithm returns correct results without reconstructing full strings explicitly.

Practice

1. You are given an integer array and asked to find all unique triplets that sum to zero. Which approach guarantees an optimal solution in terms of time complexity and handles duplicates efficiently?

easy

A. Sort the array, fix one element, and use a two-pointer approach to find pairs that sum to the negative of the fixed element, skipping duplicates.

B. Use a greedy approach by sorting and picking the smallest and largest elements to form triplets.

C. Use dynamic programming to build up solutions for smaller subsets and combine them to find triplets.

D. Use three nested loops to check all triplets and store unique sorted triplets in a set.

Solution

1. Step 1: Understand problem constraints

   We need all unique triplets summing to zero, efficiently handling duplicates.

2. Step 2: Identify approach that handles duplicates and optimizes search

   Sorting and fixing one element allows using a two-pointer approach to find pairs summing to the complement, skipping duplicates efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + two-pointer approach is O(n^2) and handles duplicates [OK]

Hint: Sorting + two-pointer handles duplicates and runs in O(n²) [OK]

Common Mistakes:

• Thinking brute force is optimal
• Using DP which doesn't fit this problem
• Greedy approach misses some triplets

2. Consider the following Python function implementing the optimal 4Sum approach. Given the input nums = [1, 0, -1, 0] and target = 0, what is the final returned list of quadruplets?

easy

A. [[-1, 0, 0, 1]]

B. [[0, 0, 0, 0]]

C. [[-1, -1, 1, 1]]

D. []

Solution

1. Step 1: Sort input and build two_sum_map

   Sorted nums = [-1, 0, 0, 1]. Pairs and sums: (-1,0)= -1, (-1,0)= -1, (-1,1)=0, (0,0)=0, (0,1)=1, (0,1)=1.

2. Step 2: Find complementary pairs summing to target=0

   Check sums and their complements: sum1=-1, sum2=1; sum1=0, sum2=0. Combine pairs ensuring no index overlap. Valid quadruplet is [-1,0,0,1].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only one quadruplet sums to zero without index overlap [OK]

Hint: Sort and check pairs sums carefully to find quadruplets [OK]

Common Mistakes:

• Confusing indices leading to duplicates or missing quadruplets

3. Consider the following Python code that reverses a list of characters recursively using two pointers. What will be the final output printed by the program?

def reverseString(s):
    def helper(left, right):
        if left >= right:
            return
        s[left], s[right] = s[right], s[left]
        helper(left + 1, right - 1)

if __name__ == "__main__":
    s = ['a', 'b', 'c', 'd']
    reverseString(s)
    print(s)

easy

A. ['d', 'b', 'c', 'a']

B. ['d', 'c', 'b', 'a']

C. ['a', 'b', 'c', 'd']

D. ['c', 'b', 'a', 'd']

Solution

1. Step 1: Trace helper calls and swaps

   Initial call helper(0,3): swap s[0] and s[3] -> ['d','b','c','a'] Next call helper(1,2): swap s[1] and s[2] -> ['d','c','b','a'] Next call helper(2,1): left >= right, stop recursion.

2. Step 2: Final array state

   The array after all swaps is ['d','c','b','a'], which is the reversed input.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   All pairs swapped correctly, final reversed array matches ['d', 'c', 'b', 'a'] [OK]

Hint: Recursive swaps from ends reverse array correctly [OK]

Common Mistakes:

• Off-by-one errors in recursion base case
• Swapping wrong indices
• Not swapping at all

4. Consider the following Python code for squaring and sorting an array in-place:

def sortedSquares(nums):
    for i in range(len(nums)):
        nums[i] = nums[i] * nums[i]
    nums.sort()
    return nums

nums = [-3, 0, 2]
print(sortedSquares(nums))

What is the output of this code?

easy

A. [9, 4, 0]

B. [9, 0, 4]

C. [0, 4, 9]

D. [4, 0, 9]

Solution

1. Step 1: Square each element

   nums becomes [9, 0, 4] after squaring -3, 0, and 2 respectively.

2. Step 2: Sort the squared array

   Sorting [9, 0, 4] results in [0, 4, 9].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Squares then sort yields sorted squares [OK]

Hint: Square then sort yields sorted squares [OK]

Common Mistakes:

• Forgetting to sort after squaring
• Mixing up order of squared elements
• Off-by-one errors in indexing

5. What is the time complexity of the optimal two-pointer solution for the Container With Most Water problem, and why?

medium

A. O(n^2) because each pointer moves multiple times and all pairs are checked.

B. O(n) because each pointer moves inward at most n times, scanning the array once.

C. O(n log n) due to sorting or binary search steps involved.

D. O(1) because only constant space and operations are used.

Solution

1. Step 1: Analyze pointer movements

   Each pointer starts at opposite ends and moves inward only when the shorter line pointer moves, so total moves per pointer ≤ n.

2. Step 2: Count total operations

   Since pointers move inward without revisiting positions, total iterations ≤ n, making time complexity O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two-pointer linear scan -> O(n) time [OK]

Hint: Two pointers each move at most n times -> O(n) [OK]

Common Mistakes:

• Assuming nested loops cause O(n²)
• Confusing space complexity with time
• Thinking sorting is required