Code Logo

Make The String Great

Published at23 Jul 2026
Created by
Easy 1 views
Like0

Given a string of letters, a bad pair is two adjacent characters where one is uppercase and the other is the same letter in lowercase (e.g., 'aA' or 'Zz'). Repeatedly remove all bad pairs. After removal, new adjacent pairs may become bad and must also be removed. A stack handles this naturally: when the top of the stack and the current character differ by exactly 32 in ASCII (the difference between upper and lowercase), they annihilate. Otherwise, push the current character. This is similar to Remove Adjacent Duplicates but with case sensitivity.

The ASCII difference between uppercase and lowercase letters is exactly 32. For example, 'A' is 65 and 'a' is 97. The absolute difference |65 - 97| = 32. This makes it easy to detect bad pairs without checking both cases explicitly. The stack approach processes each character once, comparing it with the top of the stack. If they differ by exactly 32 (same letter, different case), they cancel each other out.

This problem is commonly asked as a follow-up to Remove Adjacent Duplicates, testing whether you can adapt the same pattern to a different matching condition.

This problem tests understanding of character encoding (ASCII values) and stack operations. It is often asked as a warm-up before more complex string manipulation problems. The same pattern of matching adjacent characters with a specific condition appears in problems like Remove All Adjacent Duplicates and basic HTML tag parsing.

Example Input & Output

Example 1
Input
"abBAcC"
Output
""
Explanation

All removed.

Example 2
Input
"leEeetcode"
Output
"leetcode"
Explanation

Ee removed.

Example 3
Input
"s"
Output
"s"
Explanation

Single char.

Algorithm Flow

Recommendation Algorithm Flow for Make The String Great

Solution Approach

Remove adjacent pairs where one letter is the uppercase version of the other (like 'aA' or 'Bb') until no such pairs remain. Use a stack: for each character, if it differs from the top of the stack only by case (same letter, different case), pop the stack. Otherwise, push the character.

function makeGood(s) {
  var stack = [];
  for (var i = 0; i < s.length; i++) {
    var c = s[i];
    if (stack.length && Math.abs(c.charCodeAt(0) - stack[stack.length - 1].charCodeAt(0)) === 32) {
      stack.pop();
    } else {
      stack.push(c);
    }
  }
  return stack.join('');
}

The ASCII difference between uppercase and lowercase of the same letter is 32. Characters that differ by 32 and are adjacent in the stack annihilate each other.

Time complexity is O(n), space complexity is O(n).

Best Answers

java
import java.util.*;
class Solution {
    public String solution(String s) {
        Stack<Character> stack = new Stack<>();
        for (char ch : s.toCharArray()) {
            if (!stack.isEmpty() && Math.abs(stack.peek() - ch) == 32) stack.pop();
            else stack.push(ch);
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) sb.insert(0, stack.pop());
        return sb.toString();
    }
}