# Make The String Great
**Difficulty:** EASY
[External](https://leetcode.com/problems/make-the-string-great)
Canonical: https://scaleengineer.com/dsa/problems/make-the-string-great
**Data structures:** String, Stack
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [BlackStone](https://scaleengineer.com/companies/blackstone)
---
## Problem
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
## Brute Force with Repeated Scans
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.
**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`.
**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.
### Explanation
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.

```java
class Solution {
    public String makeGood(String s) {
        StringBuilder sb = new StringBuilder(s);
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i < sb.length() - 1; i++) {
                char curr = sb.charAt(i);
                char next = sb.charAt(i + 1);
                if (Math.abs(curr - next) == 32) {
                    sb.delete(i, i + 2);
                    changed = true;
                    // Restart scan from the beginning of the modified string
                    break;
                }
            }
        }
        return sb.toString();
    }
}
```
### 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`.

## Optimal Single-Pass Approach with a Stack
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public String makeGood(String s) {
        StringBuilder resultBuilder = new StringBuilder();
        for (char currentChar : s.toCharArray()) {
            int length = resultBuilder.length();
            if (length > 0 && Math.abs(resultBuilder.charAt(length - 1) - currentChar) == 32) {
                // Found a bad pair, remove the last character from the result
                resultBuilder.deleteCharAt(length - 1);
            } else {
                // No bad pair, add the current character to the result
                resultBuilder.append(currentChar);
            }
        }
        return resultBuilder.toString();
    }
}
```
### 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.

# Solutions
### Java

```java
class Solution {
public
  String makeGood(String s) {
    StringBuilder sb = new StringBuilder();
    for (char c : s.toCharArray()) {
      if (sb.length() == 0 || Math.abs(sb.charAt(sb.length() - 1) - c) != 32) {
        sb.append(c);
      } else {
        sb.deleteCharAt(sb.length() - 1);
      }
    }
    return sb.toString();
  }
}

```

### CPP

```cpp
class Solution {
public:
  string makeGood(string s) {
    string stk;
    for (char c : s) {
      if (stk.empty() || abs(stk.back() - c) != 32) {
        stk += c;
      } else {
        stk.pop_back();
      }
    }
    return stk;
  }
};

```

### Python

```python
class Solution:
    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)

```