Make The String Great
Easy · Stack & Strings · String · Stack
Problem
You are given a string s of uppercase and lowercase English letters. Two neighboring characters form a bad pair when they are the same letter in different cases, such as "aA" or "Bb".
Repeatedly delete any bad pair until none is left, and return the resulting string. The result is the same whatever order you delete in. An empty string is a valid answer.
Examples
Input: s = "abBAc" Output: "c"
Deleting "bB" leaves "aAc", and deleting "aA" leaves "c".
Input: s = "kK" Output: ""
The whole string is one bad pair, so the answer is the empty string.
Input: s = "Hello" Output: "Hello"
No two neighbors are the same letter in different cases.
Constraints
- 1 <= len(s) <= 100
- s contains only uppercase and lowercase English letters
Approaches
- Baseline: delete the first bad pair, rescan — time O(n²), space O(n)
Follow-up
The same stack works for any rule where a new item cancels the most recent survivor: removing equal neighbors, cancelling a move with its opposite, deleting fixed two-letter substrings. The use cases below try two of them.
Related problems
Start free on Cariara · Coding problems · System design studio
