Jobs

Interviews

Discussions

Backspace String Compare

Easy

Google

2 views

Topics:

StringsTwo Pointers

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.

For example:

s = "ab#c", t = "ad#c" should return true because both become "ac".
s = "ab##", t = "c#d#" should return true because both become "".
s = "a#c", t = "b" should return false because s becomes "c" while t becomes "b".

Could you provide a solution that is O(n) in time and O(1) in space?

Backspace String Compare

Easy

Google

2 views

Topics:

StringsTwo Pointers

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.

For example:

s = "ab#c", t = "ad#c" should return true because both become "ac".
s = "ab##", t = "c#d#" should return true because both become "".
s = "a#c", t = "b" should return false because s becomes "c" while t becomes "b".

Could you provide a solution that is O(n) in time and O(1) in 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` contain characters other than lowercase letters?
Are the backspace characters '#' only valid when they have a preceding character, or can they appear at the beginning of a string?
Can the input strings `S` and `T` be null or empty? If so, what should I return?
Is there a maximum length for the input strings `S` and `T`? This might impact space complexity considerations.
If after processing the backspaces, both strings are empty, should I return true?

Brute Force Solution

Approach

The brute force method for comparing strings with backspaces involves actually applying the backspaces and then comparing the final results. We simplify each string individually and then see if the simplified strings are identical. If they are, the original strings are considered equal.

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

Take the first string.
Go through the first string character by character.
If you see a regular character, keep it.
If you see a backspace character, remove the character that came right before it.
After processing every character, you will have a simplified version of the first string.
Repeat the same process for the second string to get its simplified version.
Finally, compare the two simplified strings to see if they are exactly the same.
If the simplified strings are the same, then the original strings are considered equal.

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:

                # Prevents popping from an empty list
                if simplified_string:

                    simplified_string.pop()

        return "".join(simplified_string)

    first_simplified_string = simplify_string(first_string)
    second_simplified_string = simplify_string(second_string)

    # Compare the simplified strings
    return first_simplified_string == second_simplified_string

Big(O) Analysis

Time Complexity

O(n^2) – We iterate through each of the two input strings, S and T, each potentially of length n. For each string, we iterate through its characters. When a backspace character is encountered, we remove a character from the simplified string, which, depending on the string implementation, can take O(n) time. Since this deletion operation can occur within the loop that iterates through the string, in the worst case (lots of backspaces), the time complexity to simplify each string is O(n^2). Finally, comparing the two simplified strings takes O(n) time, but this is dominated by the simplification step.

Space Complexity

O(N) – The provided algorithm constructs simplified strings by iterating through each input string. In the worst-case scenario, where there are no backspace characters, the simplified string will be the same length as the original. Thus, we are creating auxiliary storage for the simplified versions of the input strings, and the size of these simplified strings can grow linearly with the size of the input strings. Therefore, the algorithm's space complexity is O(N), where N represents the maximum length of the two input strings.

Optimal Solution

Approach

The key to solving this efficiently is to compare the strings from the end. We want to skip over characters that are supposed to be deleted until we find the next relevant character for comparison, working backwards through both strings simultaneously.

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

Start by looking at the end of both strings.
If you find a 'backspace' character (which deletes the preceding character), keep track of how many characters should be skipped.
As you move backward through the string, skip the next character if your 'skip count' is greater than zero, and reduce the 'skip count'.
Repeat this process until you find a character that should actually be compared (a character that isn't skipped).
Do the same thing for the other string: skip backspaced characters until you find one to compare.
If the two characters you've found (after skipping backspaces) are different, the strings aren't the same.
If both characters are the same, keep moving backwards through both strings, repeating the skipping and comparing process.
If you reach the beginning of both strings without finding any differences, the strings are the same.
If you reach the beginning of one string but not the other, and there are still valid characters to compare in the longer string, the strings aren't the same.

Code Implementation

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

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

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

        # If pointers are 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
        else:
            # Check for cases where one string is exhausted before the other
            if first_string_pointer >= 0 or second_string_pointer >= 0:
                return False

        first_string_pointer -= 1
        second_string_pointer -= 1

    # Strings are equal if all comparisons passed
    return True

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through both strings at most once. The while loop continues as long as either of the string indices are within bounds, and within the loop, each index is decremented in each iteration after processing backspaces. The skipping of characters due to backspaces does not add significant complexity because each character is visited and potentially skipped at most a constant number of times. Therefore, the overall time complexity is linear with respect to the length of the strings, denoted as O(n).

Space Complexity

O(1) – The provided algorithm operates by comparing characters from the end of the strings using index manipulation and a 'skip count' variable. It does not create any auxiliary data structures like arrays, lists, or hash maps to store intermediate results. The space used by the algorithm consists only of a few integer variables, which remains constant irrespective of the input string lengths. Therefore, the space complexity is O(1), indicating constant space.

Edge Cases

Case	How to Handle
Null or empty input strings	Return true if both are null/empty, false if one is and the other is not.
Strings containing only backspace characters	The processed string will be empty; compare two empty strings.
Strings where backspaces precede non-backspace characters at the beginning.	These leading backspaces effectively delete nothing, leaving remaining chars.
Long strings with many consecutive backspaces	Ensure algorithm has a complexity to handle large inputs efficiently.
Strings containing mixed characters including non-alphanumeric	The algorithm should treat all characters equally, irrespective of their type.
Strings where the number of backspaces exceeds the number of valid characters before it	The algorithm correctly handles this by effectively removing characters until the processed string is empty.
String with a mix of deleting and appending characters	Handle each '#' character, reducing the string size if possible, or skipping it if the string is empty.
Strings with unicode characters	The algorithm needs to handle strings with unicode characters correctly (e.g. encoded as UTF-8) to avoid unexpected results.

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` contain characters other than lowercase letters?
Are the backspace characters '#' only valid when they have a preceding character, or can they appear at the beginning of a string?
Can the input strings `S` and `T` be null or empty? If so, what should I return?
Is there a maximum length for the input strings `S` and `T`? This might impact space complexity considerations.
If after processing the backspaces, both strings are empty, should I return true?

Brute Force Solution

Approach

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

Take the first string.
Go through the first string character by character.
If you see a regular character, keep it.
If you see a backspace character, remove the character that came right before it.
After processing every character, you will have a simplified version of the first string.
Repeat the same process for the second string to get its simplified version.
Finally, compare the two simplified strings to see if they are exactly the same.
If the simplified strings are the same, then the original strings are considered equal.

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:

                # Prevents popping from an empty list
                if simplified_string:

                    simplified_string.pop()

        return "".join(simplified_string)

    first_simplified_string = simplify_string(first_string)
    second_simplified_string = simplify_string(second_string)

    # Compare the simplified strings
    return first_simplified_string == second_simplified_string

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start by looking at the end of both strings.
If you find a 'backspace' character (which deletes the preceding character), keep track of how many characters should be skipped.
As you move backward through the string, skip the next character if your 'skip count' is greater than zero, and reduce the 'skip count'.
Repeat this process until you find a character that should actually be compared (a character that isn't skipped).
Do the same thing for the other string: skip backspaced characters until you find one to compare.
If the two characters you've found (after skipping backspaces) are different, the strings aren't the same.
If both characters are the same, keep moving backwards through both strings, repeating the skipping and comparing process.
If you reach the beginning of both strings without finding any differences, the strings are the same.
If you reach the beginning of one string but not the other, and there are still valid characters to compare in the longer string, the strings aren't the same.

Code Implementation

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

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

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

        # If pointers are 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
        else:
            # Check for cases where one string is exhausted before the other
            if first_string_pointer >= 0 or second_string_pointer >= 0:
                return False

        first_string_pointer -= 1
        second_string_pointer -= 1

    # Strings are equal if all comparisons passed
    return True

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input strings	Return true if both are null/empty, false if one is and the other is not.
Strings containing only backspace characters	The processed string will be empty; compare two empty strings.
Strings where backspaces precede non-backspace characters at the beginning.	These leading backspaces effectively delete nothing, leaving remaining chars.
Long strings with many consecutive backspaces	Ensure algorithm has a complexity to handle large inputs efficiently.
Strings containing mixed characters including non-alphanumeric	The algorithm should treat all characters equally, irrespective of their type.
Strings where the number of backspaces exceeds the number of valid characters before it	The algorithm correctly handles this by effectively removing characters until the processed string is empty.
String with a mix of deleting and appending characters	Handle each '#' character, reducing the string size if possible, or skipping it if the string is empty.
Strings with unicode characters	The algorithm needs to handle strings with unicode characters correctly (e.g. encoded as UTF-8) to avoid unexpected results.