Jobs

Interviews

Discussions

Backspace String Compare

Easy

Grammarly

0 views

Topics:

StringsTwo PointersStacks

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example 1:

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

Example 2:

Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".

Example 3:

Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

Constraints:

1 <= s.length, t.length <= 200
s and t only contain lowercase letters and '#' characters.

Follow up: Can you solve it in O(n) time and O(1) space?

Backspace String Compare

Easy

Grammarly

0 views

Topics:

StringsTwo PointersStacks

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example 1:

Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

Example 2:

Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".

Example 3:

Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

Constraints:

1 <= s.length, t.length <= 200
s and t only contain lowercase letters and '#' characters.

Follow up: Can you solve it in O(n) time and O(1) space?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings `s` and `t` be empty or null?
Are the input strings guaranteed to only contain alphanumeric characters and the '#' character, or can they contain other special characters?
What is the maximum length of the input strings `s` and `t`?
If a '#' character appears at the beginning of a string or when there are no characters to backspace, how should it be handled?
Are there any memory constraints I should be aware of, or is it acceptable to modify the input strings directly?

Brute Force Solution

Approach

The brute force method focuses on simplifying the problem first. For each string, simulate the effect of the backspaces to get the final form of the string, then just compare the final forms of the two strings.

Here's how the algorithm would work step-by-step:

For the first string, go through it from beginning to end.
Whenever you see a regular letter, keep it in a separate container.
If you encounter a backspace character, remove the last letter from the container, if there is one.
After you have processed the entire first string, you will have a simplified version.
Repeat the same process for the second string to also get its simplified version.
Finally, compare the simplified versions of the two strings. If they are exactly the same, then the original strings are considered equal with respect to the backspace operations.

Code Implementation

def backspace_string_compare_brute_force(first_string, second_string):

    def simplify_string(input_string):
        simplified_string = []

        for character in input_string:
            if character != '#':
                simplified_string.append(character)

            # Handle backspace character
            else:

                # Removing the last character
                if simplified_string:
                    simplified_string.pop()

        return "".join(simplified_string)

    # Simplifying the first string
    simplified_first_string = simplify_string(first_string)

    # Simplifying the second string
    simplified_second_string = simplify_string(second_string)

    # Comparing the two strings
    return simplified_first_string == simplified_second_string

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each string once to process characters and backspaces. For a string of length n, the algorithm visits each of the n characters. Creating the simplified strings takes O(n) time for each string. Comparing the two simplified strings also takes O(n) time in the worst case, where n is the maximum length of the two simplified strings. Thus the overall time complexity is O(n).

Space Complexity

O(N) – The algorithm uses separate containers (e.g., lists or strings) to store the simplified versions of the input strings. In the worst case, where there are no backspace characters in the input string, the container for each string could grow to the size of the original string itself. Thus, the auxiliary space required to store the simplified strings depends linearly on the size of the input strings, where N is the length of the longest input string. Therefore, the space complexity is O(N).

Optimal Solution

Approach

The trick is to process both strings backwards, one character at a time. The clever part is to keep track of backspaces encountered, skipping characters that should be deleted.

Here's how the algorithm would work step-by-step:

Start reading both strings from their very ends.
Keep track of how many backspaces you've seen in each string.
If you see a normal character and you have backspaces waiting to be used, then use a backspace by decreasing its count.
If a character isn't skipped by a backspace, then it's a character you should consider for the comparison.
If you've skipped all the characters a backspace applies to, reset it to zero.
Now, compare the relevant characters in both strings. If the characters are different, the strings aren't equal.
If you reach the beginning of one string while there are still relevant characters left in the other string, they are not equal.
If you process both strings entirely and all relevant characters were equal, then the strings are considered equal.

Code Implementation

def backspace_string_compare(first_string, second_string):
    first_string_pointer = len(first_string) - 1
    second_string_pointer = len(second_string) - 1
    first_string_backspace_count = 0
    second_string_backspace_count = 0

    while first_string_pointer >= 0 or second_string_pointer >= 0:
        while first_string_pointer >= 0:
            if first_string[first_string_pointer] == '#':
                first_string_backspace_count += 1
                first_string_pointer -= 1
            elif first_string_backspace_count > 0:
                first_string_backspace_count -= 1
                first_string_pointer -= 1
            else:
                break

        while second_string_pointer >= 0:
            if second_string[second_string_pointer] == '#':
                second_string_backspace_count += 1
                second_string_pointer -= 1
            elif second_string_backspace_count > 0:
                second_string_backspace_count -= 1
                second_string_pointer -= 1
            else:
                break

        # If either pointer is still in bounds, compare chars
        if first_string_pointer >= 0 and second_string_pointer >= 0:
            if first_string[first_string_pointer] != second_string[second_string_pointer]:
                return False

        # Strings are not equal if one pointer is still in bounds
        else:
            if first_string_pointer >= 0 or second_string_pointer >= 0:
                return False

        first_string_pointer -= 1
        second_string_pointer -= 1

    # Strings are equal
    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each string at most once, processing characters from the end to the beginning. The while loop condition ensures that both strings are traversed until the end or a mismatch is found. The number of operations is directly proportional to the length of the longer string, where n represents the length of the longer string. Therefore, the time complexity is O(n).

Space Complexity

O(1) – The provided algorithm processes the strings in place using a constant number of variables to track the current index and backspace counts for each string. No auxiliary data structures, such as temporary lists or hash maps, are used to store intermediate results. Therefore, the extra space used does not depend on the input size N, where N is the total length of the input strings. The algorithm maintains a constant auxiliary space complexity.

Edge Cases

Case	How to Handle
Empty strings as input	Should return true if both strings are empty, false if only one is empty, and handle correctly the cases where backspaces delete all characters.
Strings containing only backspaces	Should result in empty strings and be handled gracefully.
Strings with leading or trailing backspaces	The solution should process leading and trailing backspaces correctly.
Strings where backspaces delete across multiple characters	The algorithm must repeatedly apply the backspace until it reaches the beginning of the string or a non-backspace character.
Very long strings to test for time complexity	The solution needs to efficiently process long strings, ideally in linear time.
Strings with many consecutive backspaces	The algorithm needs to be able to correctly handle a large number of consecutive backspace characters without causing stack overflow or excessive computation.
Strings with interleaved characters and backspaces	The solution should correctly process mixed sequences of characters and backspaces.
Strings that result in an empty string after backspace operations	The algorithm should handle the case where the reduced string is empty after processing backspaces.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input strings `s` and `t` be empty or null?
Are the input strings guaranteed to only contain alphanumeric characters and the '#' character, or can they contain other special characters?
What is the maximum length of the input strings `s` and `t`?
If a '#' character appears at the beginning of a string or when there are no characters to backspace, how should it be handled?
Are there any memory constraints I should be aware of, or is it acceptable to modify the input strings directly?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

For the first string, go through it from beginning to end.
Whenever you see a regular letter, keep it in a separate container.
If you encounter a backspace character, remove the last letter from the container, if there is one.
After you have processed the entire first string, you will have a simplified version.
Repeat the same process for the second string to also get its simplified version.
Finally, compare the simplified versions of the two strings. If they are exactly the same, then the original strings are considered equal with respect to the backspace operations.

Code Implementation

def backspace_string_compare_brute_force(first_string, second_string):

    def simplify_string(input_string):
        simplified_string = []

        for character in input_string:
            if character != '#':
                simplified_string.append(character)

            # Handle backspace character
            else:

                # Removing the last character
                if simplified_string:
                    simplified_string.pop()

        return "".join(simplified_string)

    # Simplifying the first string
    simplified_first_string = simplify_string(first_string)

    # Simplifying the second string
    simplified_second_string = simplify_string(second_string)

    # Comparing the two strings
    return simplified_first_string == simplified_second_string

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

The trick is to process both strings backwards, one character at a time. The clever part is to keep track of backspaces encountered, skipping characters that should be deleted.

Here's how the algorithm would work step-by-step:

Start reading both strings from their very ends.
Keep track of how many backspaces you've seen in each string.
If you see a normal character and you have backspaces waiting to be used, then use a backspace by decreasing its count.
If a character isn't skipped by a backspace, then it's a character you should consider for the comparison.
If you've skipped all the characters a backspace applies to, reset it to zero.
Now, compare the relevant characters in both strings. If the characters are different, the strings aren't equal.
If you reach the beginning of one string while there are still relevant characters left in the other string, they are not equal.
If you process both strings entirely and all relevant characters were equal, then the strings are considered equal.

Code Implementation

def backspace_string_compare(first_string, second_string):
    first_string_pointer = len(first_string) - 1
    second_string_pointer = len(second_string) - 1
    first_string_backspace_count = 0
    second_string_backspace_count = 0

    while first_string_pointer >= 0 or second_string_pointer >= 0:
        while first_string_pointer >= 0:
            if first_string[first_string_pointer] == '#':
                first_string_backspace_count += 1
                first_string_pointer -= 1
            elif first_string_backspace_count > 0:
                first_string_backspace_count -= 1
                first_string_pointer -= 1
            else:
                break

        while second_string_pointer >= 0:
            if second_string[second_string_pointer] == '#':
                second_string_backspace_count += 1
                second_string_pointer -= 1
            elif second_string_backspace_count > 0:
                second_string_backspace_count -= 1
                second_string_pointer -= 1
            else:
                break

        # If either pointer is still in bounds, compare chars
        if first_string_pointer >= 0 and second_string_pointer >= 0:
            if first_string[first_string_pointer] != second_string[second_string_pointer]:
                return False

        # Strings are not equal if one pointer is still in bounds
        else:
            if first_string_pointer >= 0 or second_string_pointer >= 0:
                return False

        first_string_pointer -= 1
        second_string_pointer -= 1

    # Strings are equal
    return True

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty strings as input	Should return true if both strings are empty, false if only one is empty, and handle correctly the cases where backspaces delete all characters.
Strings containing only backspaces	Should result in empty strings and be handled gracefully.
Strings with leading or trailing backspaces	The solution should process leading and trailing backspaces correctly.
Strings where backspaces delete across multiple characters	The algorithm must repeatedly apply the backspace until it reaches the beginning of the string or a non-backspace character.
Very long strings to test for time complexity	The solution needs to efficiently process long strings, ideally in linear time.
Strings with many consecutive backspaces	The algorithm needs to be able to correctly handle a large number of consecutive backspace characters without causing stack overflow or excessive computation.
Strings with interleaved characters and backspaces	The solution should correctly process mixed sequences of characters and backspaces.
Strings that result in an empty string after backspace operations	The algorithm should handle the case where the reduced string is empty after processing backspaces.