Code Logo

Make The String Great

Published at23 Jul 2026
Created by
Easy 0 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
Recommendation Algorithm Flow for Make The String Great

Solution Approach

Iterate through characters. If stack non-empty and ASCII difference === 32, pop. Else push. Join at end.

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

Time O(n), Space 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();
    }
}