Amazon SDE Intern Interview Question

844. Backspace String Compare

Difficulty: Easy
Tags: Stack, Two Pointers, String, Simulation
LeetCode Link

Problem Description

This problem involves comparing two strings to determine if they are the same after processing all backspace operations. In these 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.

Example:

• For 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 perform 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 the screen without building the resultant strings.

Key Steps:

1. Start by pointing at the last characters of both s and t.
2. Move backward through each string. Whenever you encounter a #, skip the next non-# character.
3. Compare characters at the current position in both strings if they are not skipped.
4. If both pointers reach the beginning without finding any mismatch, return true.

Solution Approach

The implementation uses a two-pointer approach:

• Initialize pointers i and j to the last indices of s and t, respectively.
• Use two variables skipS and skipT to keep track of the number of backspaces encountered.
• Use a while loop to walk through both strings concurrently until both pointers reach the beginning.
• Compare the characters from each string that are at the current positions.
• Return false if any discrepancies are found.

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.

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

Processing Steps:

• Iteration 1: Both strings encounter #, incrementing their respective skip counters.
• Iteration 2: Skip over characters based on the counts and compare.
• Conclusion: If the pointers end up pointing to different characters or one is out of bounds while the other isn't, return false.

Solution Implementation

Here’s the Java implementation of the solution:

class Solution {
    public boolean backspaceCompare(String s, String t) {
        int i = s.length() - 1; // Pointer for string s
        int j = t.length() - 1; // Pointer for string t
        int skipS = 0; // Skip count for string s
        int skipT = 0; // Skip count for string t

        while (i >= 0 || j >= 0) {
            // Process string s
            while (i >= 0) {
                if (s.charAt(i) == '#') {
                    skipS++; // Increment skip count for #
                    i--;
                } else if (skipS > 0) {
                    skipS--; // Skip this character
                    i--;
                } else {
                    break; // Found a valid character
                }
            }

            // Process string t
            while (j >= 0) {
                if (t.charAt(j) == '#') {
                    skipT++; // Increment skip count for #
                    j--;
                } else if (skipT > 0) {
                    skipT--; // Skip this character
                    j--;
                } else {
                    break; // Found a valid character
                }
            }

            // Compare characters from both strings
            if (i >= 0 && j >= 0) {
                if (s.charAt(i) != t.charAt(j)) {
                    return false; // Characters do not match
                }
            } else if (i >= 0 || j >= 0) {
                return false; // One string has more characters
            }

            // Move to the next character
            i--;
            j--;
        }

        return true; // All characters matched
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.backspaceCompare("ab#c", "ad#c")); // Output: true
        System.out.println(sol.backspaceCompare("ab##", "c#d#")); // Output: true
        System.out.println(sol.backspaceCompare("a#c", "b")); // Output: false
    }
}