1544. Make The String Great


Problem Description

The problem requires us to cleanse a given string s consisting of both uppercase and lowercase English letters such that no two adjacent characters are a pair of the same letter in different cases (i.e., 'a' and 'A'). If such a pair exists, those two characters are considered bad and need to be removed. We start by identifying these bad pairs and continue removing them until there are no more such pairs, resulting in a 'good' string. The output is the 'good' string which does not contain any bad pairs. It's also noted that an empty string qualifies as a good string.

Intuition

The idea behind the given solution approach is to use a stack, which is a Last-In, First-Out data structure, to help detect and remove the bad pairs. Here's the step-by-step process to understand the intuition:

  • Iterate through the given string character by character.
  • If the current character, when paired with the last character in the stack (if any), does not form a bad pair, push it onto the stack.
  • A 'bad pair' is defined as two adjacent characters where one is an uppercase letter and the other is a lowercase letter of the same kind (the difference in their ASCII values would be exactly 32 if one is uppercase and the other is lowercase).
  • If a 'bad pair' is detected (checked by seeing if the ASCII value difference is 32), remove the top element from the stack, effectively deleting both characters from consideration.
  • Continue this process until we have iterated through all characters in the string.
  • Convert the stack to a string and return it as it represents the 'good' string free of bad pairs.

The key to this solution is recognizing that a stack is an ideal way to keep track of characters, as it allows us to easily add new characters or remove the last added character when we find a matching pair that should be eliminated.

Solution Approach

The solution employs a stack to manage the removal of bad pairs effectively. Here's a more detailed breakdown of the implementation:

  1. Initialize an empty stack called stk.
  2. Iterate through each character c in the input string s.
  3. For each character:
    • Check if the stack is empty or not. Continue to the next step if it's not empty. If it is empty, push the current character onto the stack.
    • Calculate the absolute difference of ASCII values between the current character c and the character at the top of the stack stk[-1].
    • If the absolute difference is 32, this means that the current character c and the top character on the stack are a bad pair. In this case, invoke stk.pop() to remove the last character from the stack, effectively eliminating the bad pair.
    • If the absolute difference is not 32, push the current character onto the stack, as it can't form a bad pair with the previous one.
  4. Once the iteration is complete, all bad pairs would have been removed, and the stack will only contain the characters of the good string.
  5. Convert the stack into a string by joining all characters in the stack using "".join(stk).
  6. Return the resulting good string.

Here is the code for the reference solution that implements this approach:

1class Solution:
2    def makeGood(self, s: str) -> str:
3        stk = []  # A stack to store the characters
4        for c in s:  # Iterate over each character in the string
5            # If the stack is not empty and the current and top characters are a bad pair
6            if stk and abs(ord(stk[-1]) - ord(c)) == 32:
7                stk.pop()  # Remove the top character from the stack
8            else:
9                stk.append(c)  # Push the current character onto the stack
10        return "".join(stk)  # Return the good string by joining the stack

This algorithm has a time complexity of O(n), where n is the length of the string, since we traverse the string once. The space complexity is O(n) as well in the worst case when there are no bad pairs, as all characters will be in the stack. However, in practice, the stack size will often be smaller than the input string because bad pairs will be removed during processing.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach:

Given the input string s = "aAbBcC", we aim to remove all bad pairs as per the rules.

Initialize an empty stack stk.

Iterate through the string:

  1. For the first character a, the stack is empty, so we push a onto the stk.
  2. For the second character A, we check with the top of the stack stk[-1] = a. The ASCII value difference between a and A is 32, so this is a bad pair. We pop a from the stack.
  3. Now, we proceed to b. The stack is empty, so we push b.
  4. Next, we go to B. It forms a bad pair with b (difference in ASCII value is 32). We pop b from the stack.
  5. We move to c. The stack is empty, so c is pushed onto the stack.
  6. Finally, for C, the stack contains c, and again, the ASCII values of C and c are 32 units apart. This is a bad pair, so we pop c from the stack.

At the end of the iteration, the stack is empty, indicating all characters formed bad pairs and have been removed.

The final 'good' string is then returned by joining all characters in the stack, which is an empty string in this case: "".join(stk), hence the result is "".

This walk-through demonstrates how the stack helps in eliminating bad pairs efficiently, resulting in a cleaned string that contains no bad pairs, which is the expected output of the algorithm.

Python Solution

1class Solution:
2    def makeGood(self, s: str) -> str:
3        # Initialize a stack to keep track of characters
4        stack = []
5      
6        # Iterate over each character in the provided string
7        for char in s:
8            # If the stack is not empty and the ASCII difference between 
9            # the current character and the last character in the stack is 32,
10            # it means they are equal but with different cases (e.g., 'a' and 'A').
11            if stack and abs(ord(stack[-1]) - ord(char)) == 32:
12                # Since the characters are a bad pair (equal but different cases),
13                # we pop the last character from the stack to "eliminate" the pair
14                stack.pop()
15            else:
16                # If the stack is empty or the characters are not a bad pair,
17                # push the current character onto the stack
18                stack.append(char)
19      
20        # Join the characters in the stack to form the "good" string
21        # and return it
22        return "".join(stack)
23

Java Solution

1// Solution class to provide a method that makes the string "good" as per given conditions
2class Solution {
3    // Method to remove instances where a letter and its opposite case letter are adjacent
4    public String makeGood(String str) {
5        // StringBuilder to efficiently manipulate strings
6        StringBuilder stringBuilder = new StringBuilder();
7      
8        // Loop through all characters in the input string
9        for (char currentChar : str.toCharArray()) {
10            // Check if stringBuilder is empty or if the last character does not cancel out with currentChar
11            // The condition checks ASCII value difference: 32 is the difference between lower and uppercase letters
12            if (stringBuilder.length() == 0 || Math.abs(stringBuilder.charAt(stringBuilder.length() - 1) - currentChar) != 32) {
13                // If they do not cancel, append current character to stringBuilder
14                stringBuilder.append(currentChar);
15            } else {
16                // If they cancel, remove the last character from stringBuilder
17                stringBuilder.deleteCharAt(stringBuilder.length() - 1);
18            }
19        }
20        // Return the "good" string after all cancellations are done
21        return stringBuilder.toString();
22    }
23}
24

C++ Solution

1class Solution {
2public:
3    // Function to remove characters that are the same letter but opposite case adjacent to each other.
4    string makeGood(string s) {
5        string stack; // Using a string to simulate a stack
6
7        // Iterate over each character in the input string
8        for (char c : s) {
9            // If the stack is empty or the absolute difference
10            // between the ASCII values of the top character in the stack
11            // and the current character is not 32 (difference between lower case and upper case),
12            // then push the current character onto the stack.
13            if (stack.empty() || abs(stack.back() - c) != 32) {
14                stack += c;
15            } else {
16                // If the top character of the stack is of opposite case but same letter as 
17                // the current character, pop the top character from the stack.
18                stack.pop_back();
19            }
20        }
21
22        // Return the resulting string after stack simulation, which is the "good" string.
23        return stack;
24    }
25};
26

Typescript Solution

1// Function to remove characters that are the same letter but opposite case adjacent to each other.
2function makeGood(s: string): string {
3    let stack: string = ''; // Using a string to simulate a stack
4
5    // Iterate over each character in the input string
6    for (let i = 0; i < s.length; i++) {
7        const currentChar: string = s[i];
8
9        // Check if the stack is not empty
10        if (stack) {
11            // Calculate the ASCII values difference between the top character of the stack and the current character
12            const diff: number = Math.abs(stack.charCodeAt(stack.length - 1) - currentChar.charCodeAt(0));
13          
14            // If the absolute difference is 32 (difference between lower case and upper case),
15            // then we found same letter but opposite case adjacent to each other.
16            if (diff === 32) {
17                // Remove the last character from the stack, which is equivalent to popping from the stack
18                stack = stack.substring(0, stack.length - 1);
19                continue; // Move to the next iteration
20            }
21        }
22      
23        // If the stack is empty or the letter cases do not cancel each other,
24        // add the current character to the stack.
25        stack += currentChar;
26    }
27
28    // Return the resulting string after stack simulation, which is the "good" string.
29    return stack;
30}
31
32// You can now call the function with a string argument to use it.
33const result: string = makeGood("aAbBcC");
34console.log(result); // Expected output: ""
35

Time and Space Complexity

Time Complexity:

The time complexity of the given function is O(n), where n is the length of the string s. Each character in the string is processed exactly once when it is iterated over and potentially processed a second time if it is popped from the stack. Since each character is pushed onto and popped from the stack at most once, the number of operations for each character is constant. Hence, the time complexity is linear with respect to the size of the input string.

Space Complexity:

The space complexity of the function is also O(n). In the worst case, the stack stk might need to store all characters of the string if they are all unique and none of them is the opposite case of the neighboring character. For instance, an input like "abcdef" would result in all characters being pushed onto the stack before the function completes. Therefore, the space required is directly proportional to the input size, leading to a linear space complexity.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫