Make The String Great

Easy

#1422Time: O(N^2), where N is the length of the string. In the worst-case scenario (e.g., a string like "abBAcC..."), we might remove only one pair per pass. Each pass involves iterating up to N characters, and the `delete` operation on a `StringBuilder` can take O(N) time. Since there can be up to N/2 pairs to remove, the total time complexity is O(N * N).Space: O(N), where N is the length of the input string. This space is used to store the `StringBuilder`.2 companies

Data structures

String Stack

Companies

Accenture BlackStone

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We repeatedly scan the string, and whenever we find a "bad" adjacent pair of characters (e.g., 'a' and 'A'), we remove them. After each removal, we restart the scan from the beginning of the modified string to ensure that new adjacent pairs created by the removal are also handled. This process continues until a full scan of the string reveals no bad pairs.

Algorithm

Convert the input string s into a StringBuilder to allow for efficient modifications.
Use a while loop that continues as long as a bad pair is found and removed in a pass. A boolean flag can track this.
In each pass, iterate through the StringBuilder from the beginning to find the first adjacent bad pair.
A pair of characters at indices i and i+1 is considered "bad" if they are the same letter but with different cases. This can be checked by seeing if the absolute difference of their ASCII values is 32.
If a bad pair is found, remove the two characters from the StringBuilder.
Set the flag to indicate a change was made and break the inner loop to restart the scan from the beginning of the now-modified string.
If a full pass is completed with no removals, the string is "good," and the outer loop terminates.
Return the final string from the StringBuilder.

Walkthrough

In this method, we use a StringBuilder for mutable string operations. The core of the logic is a while loop that continues as long as we are making changes to the string. Inside this loop, we iterate through the string with a for loop to find an adjacent pair of characters where Math.abs(char1 - char2) == 32. Once such a pair is found, we delete it from the StringBuilder, set a flag indicating a change was made, and break the inner loop. The outer while loop then causes the scan to restart from the beginning. If the inner for loop completes without finding any bad pairs, the flag remains false, the while loop terminates, and the resulting "good" string is returned.

1class Solution {2    public String makeGood(String s) {3        StringBuilder sb = new StringBuilder(s);4        boolean changed = true;5        while (changed) {6            changed = false;7            for (int i = 0; i < sb.length() - 1; i++) {8                char curr = sb.charAt(i);9                char next = sb.charAt(i + 1);10                if (Math.abs(curr - next) == 32) {11                    sb.delete(i, i + 2);12                    changed = true;13                    // Restart scan from the beginning of the modified string14                    break;15                }16            }17        }18        return sb.toString();19    }20}

Complexity

Time

O(N^2), where N is the length of the string. In the worst-case scenario (e.g., a string like "abBAcC..."), we might remove only one pair per pass. Each pass involves iterating up to N characters, and the `delete` operation on a `StringBuilder` can take O(N) time. Since there can be up to N/2 pairs to remove, the total time complexity is O(N * N).

Space

O(N), where N is the length of the input string. This space is used to store the `StringBuilder`.

Trade-offs

Pros

It's a straightforward simulation of the process described in the problem statement.
The logic is easy to understand and implement.

Cons

The time complexity is quadratic, O(N^2), which is inefficient for very large strings.
Restarting the scan from the beginning after every single removal is redundant work, as changes are localized.

A more efficient and optimal approach uses a stack. The problem involves removing adjacent items, which suggests that the last valid character we've seen is the only one that matters for the next character. This Last-In-First-Out (LIFO) behavior is perfectly modeled by a stack. We can iterate through the string just once, using the stack to build the final "good" string. A StringBuilder can be used as a highly efficient stack for this purpose.

Algorithm

Initialize an empty StringBuilder which will act as a stack and also build our result string.
Iterate through each character c of the input string s.
For each character c, check if the StringBuilder is not empty and if its last character forms a bad pair with c (i.e., Math.abs(lastChar - c) == 32).
If it's a bad pair, it means the current character c and the last character in our result cancel each other out. So, we delete the last character from the StringBuilder.
Otherwise (if the StringBuilder is empty or the characters don't form a bad pair), we append the current character c to the StringBuilder.
After the loop finishes, the StringBuilder contains the final "good" string. Return its string representation.

Walkthrough

We process the input string character by character in a single pass. We use a StringBuilder which acts like a character stack. For each character from the input, we compare it with the last character added to our StringBuilder (if any). If they form a bad pair, we pop the last character from the StringBuilder by deleting it. If they don't form a bad pair, or if the StringBuilder is empty, we push the current character onto our stack by appending it. This ensures that at any point, the StringBuilder only contains a "good" prefix. After iterating through the entire input string, the StringBuilder holds the final result.

1class Solution {2    public String makeGood(String s) {3        StringBuilder resultBuilder = new StringBuilder();4        for (char currentChar : s.toCharArray()) {5            int length = resultBuilder.length();6            if (length > 0 && Math.abs(resultBuilder.charAt(length - 1) - currentChar) == 32) {7                // Found a bad pair, remove the last character from the result8                resultBuilder.deleteCharAt(length - 1);9            } else {10                // No bad pair, add the current character to the result11                resultBuilder.append(currentChar);12            }13        }14        return resultBuilder.toString();15    }16}

Complexity

Time

O(N), where N is the length of the string. We iterate through the string's characters only once. Each character is appended to the `StringBuilder` at most once, and deleted at most once. Both `append` and `deleteCharAt` at the end of a `StringBuilder` are amortized O(1) operations.

Space

O(N), where N is the length of the string. In the worst case (a string with no bad pairs), the `StringBuilder` will grow to the size of the input string to store the result.

Trade-offs

Pros

Optimal time complexity of O(N) due to a single pass over the string.
Elegant and clean solution that correctly handles the cascading nature of removals.
More efficient than the brute-force approach for larger inputs.

Cons

Requires O(N) auxiliary space for the stack or StringBuilder. However, this is generally unavoidable as a new string must be constructed and returned.

Solutions

Solution

1class Solution {2public3  String makeGood(String s) {4    StringBuilder sb = new StringBuilder();5    for (char c : s.toCharArray()) {6      if (sb.length() == 0 || Math.abs(sb.charAt(sb.length() - 1) - c) != 32) {7        sb.append(c);8      } else {9        sb.deleteCharAt(sb.length() - 1);10      }11    }12    return sb.toString();13  }14}

1class Solution {2public:3  string makeGood(string s) {4    string stk;5    for (char c : s) {6      if (stk.empty() || abs(stk.back() - c) != 32) {7        stk += c;8      } else {9        stk.pop_back();10      }11    }12    return stk;13  }14};

1class Solution:2    def makeGood(self, s: str) -> str: stk = [] for c in s: if not stk or abs(ord(stk[- 1]) - ord(c)) != 32: stk . append(c) else: stk . pop() return "" . join(stk)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem