Make The String Great

Easy

Asked by:

102 views

Topics:

StringsStacks

Given a string s of lower and upper case English letters.

A good string is a string which doesn't have two adjacent characters s[i] and s[i + 1] where:

0 <= i <= s.length - 2
s[i] is a lower-case letter and s[i + 1] is the same letter but in upper-case or vice-versa.

To make the string good, you can choose two adjacent characters that make the string bad and remove them. You can keep doing this until the string becomes good.

Return the string after making it good. The answer is guaranteed to be unique under the given constraints.

Notice that an empty string is also good.

Example 1:

Input: s = "leEeetcode"
Output: "leetcode"
Explanation: In the first step, either you choose i = 1 or i = 2, both will result "leEeetcode" to be reduced to "leetcode".

Example 2:

Input: s = "abBAcC"
Output: ""
Explanation: We have many possible scenarios, and all lead to the same answer. For example:
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""

Example 3:

Input: s = "s"
Output: "s"

Constraints:

1 <= s.length <= 100
s contains only lower and upper case English letters.

Try coding it in LeetCode

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:

What characters are allowed in the string? Is it limited to just uppercase and lowercase English letters?
If the string is already 'great' (contains no bad pairs), what should the output be? The original string or an empty string?
Is the comparison case-sensitive? For example, does 'aA' form a bad pair, but 'Aa' does not?
What should I return if the input string is null or empty?
Are there any length limitations on the input string?

Brute Force Solution

Approach

The goal is to clean up a string by repeatedly removing pairs of characters that are the same letter but different cases (like 'a' and 'A'). The brute force method involves checking and removing these pairs over and over until no more pairs can be removed.

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

Begin with the original string.
Look at every pair of adjacent characters in the string to see if they are the same letter but opposite cases (e.g., 'a' and 'A', or 'B' and 'b').
If you find such a pair, remove both characters from the string.
Now, repeat the entire process from the beginning, starting with this newly shortened string.
Keep doing this until you go through the whole string and find absolutely no pairs of characters that need to be removed.
At that point, the string is 'great' according to the problem definition, and you have your final answer.

Code Implementation

def make_the_string_great_brute_force(input_string):
    string_changed = True

    while string_changed:
        string_changed = False
        new_string = ""
        index = 0

        while index < len(input_string):
            # Check for adjacent characters that need removal
            if index + 1 < len(input_string) and \
               input_string[index].lower() == input_string[index + 1].lower() and \
               input_string[index] != input_string[index + 1]:

                # A pair was found, so skip both characters
                index += 2
                string_changed = True

            else:
                # Keep the current character if no match is found
                new_string += input_string[index]
                index += 1

        # Update the string for the next iteration
        input_string = new_string

    return input_string

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm iterates through the string of length n potentially multiple times. In the worst case, each removal of a pair might require rescanning almost the entire string. Since in the worst-case scenario where alternating problematic characters are scattered across the string, up to n/2 removals may be required. Therefore, the outer loop for repeated processing has a complexity of O(n) and the inner loop to find and remove the bad characters has complexity O(n). Thus, the overall time complexity becomes O(n*n) which simplifies to O(n^2).

Space Complexity

O(N) – The described iterative approach modifies the string in place conceptually. However, in many string implementations, repeated removals can create new string objects or copies behind the scenes, even if the original string object is seemingly modified. Because the worst case involves repeatedly removing characters, potentially resulting in the creation of N/2 intermediate string objects, where N is the length of the input string, the auxiliary space could grow linearly with the input size. Thus, the space complexity is O(N).

Optimal Solution

Approach

The goal is to remove adjacent letter pairs from a string if they are the same letter but different cases (one uppercase, one lowercase). The key is to keep track of the characters we've seen so far and quickly check for these bad pairs as we go.

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

Go through the string one character at a time, from left to right.
Imagine you have a stack of characters. For each character in the string, check if it forms a 'bad pair' with the character at the top of the stack. A 'bad pair' is the same letter in different cases.
If a character does form a 'bad pair' with the top of the stack, remove (pop) the top character from the stack (effectively deleting both characters).
If a character does not form a 'bad pair' with the top of the stack, add (push) the current character to the top of the stack.
Continue this process until you have gone through the entire string.
The characters remaining in the stack, when combined together, will be the 'great' string.

Code Implementation

def make_the_string_great(input_string):
    character_stack = []

    for current_character in input_string:
        # Check if the stack is not empty
        if character_stack:
            top_of_stack = character_stack[-1]

            # Check if the current character forms a bad pair with the top of the stack
            if (current_character.islower() and top_of_stack.isupper() and current_character.upper() == top_of_stack) or \
               (current_character.isupper() and top_of_stack.islower() and current_character.lower() == top_of_stack):
                # Remove the top character from the stack
                character_stack.pop()

            else:
                # Add the current character to the stack
                character_stack.append(current_character)

        else:
            # Add the current character to the stack if stack is empty
            character_stack.append(current_character)

    # Construct the great string from the remaining characters in the stack
    return "".join(character_stack)

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n once. For each character, it performs a constant-time operation (checking for a 'bad pair' against the top of the stack and either pushing or popping). The stack operations (push and pop) are also constant time. Therefore, the time complexity is directly proportional to the length of the input string, resulting in O(n).

Space Complexity

O(N) – The provided solution uses a stack to keep track of characters. In the worst-case scenario, where no adjacent characters form 'bad pairs', all N characters of the input string will be pushed onto the stack. Thus, the auxiliary space required grows linearly with the input size N, as the stack's size can reach N. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Empty input string	Return an empty string immediately as there's nothing to process.
String with a single character	Return the single-character string as it cannot be 'made bad'.
String with two characters that cancel each other out	Return an empty string as the two characters negate each other.
String with no 'bad' character pairs	Return the original string, as no removals are necessary.
String with maximum allowed length	Ensure the solution's time and space complexity allow for processing without exceeding memory or time limits.
String where all characters are the same case (all uppercase or all lowercase)	The algorithm should recognize there are no cancelling pairs and return the original string.
Alternating pairs of bad characters resulting in continuous cancellations	The stack-based approach correctly handles iterative cancellations.
Very long string with many cancelling pairs close to the beginning, requiring repeated removals	The solution should efficiently handle a large number of removals, preventing performance degradation.

Empty input string

How to Handle:

Return an empty string immediately as there's nothing to process.

String with a single character

How to Handle:

Return the single-character string as it cannot be 'made bad'.

String with two characters that cancel each other out

How to Handle:

Return an empty string as the two characters negate each other.

String with no 'bad' character pairs

How to Handle:

Return the original string, as no removals are necessary.

String with maximum allowed length

How to Handle:

Ensure the solution's time and space complexity allow for processing without exceeding memory or time limits.

String where all characters are the same case (all uppercase or all lowercase)

How to Handle:

The algorithm should recognize there are no cancelling pairs and return the original string.

Alternating pairs of bad characters resulting in continuous cancellations

How to Handle:

The stack-based approach correctly handles iterative cancellations.

Very long string with many cancelling pairs close to the beginning, requiring repeated removals

How to Handle:

The solution should efficiently handle a large number of removals, preventing performance degradation.