Make The String Great

Easy
375.

Make The String Great

Make The String Great is an easy coding problem on strings and stack, asked in Amazon and Adobe interviews.

A string is good if it contains no two adjacent characters s[i] and s[i+1] where one is the lowercase and the other the uppercase form of the same letter.

Repeatedly delete such a pair until the string is good, and return the result. The answer is unique regardless of the order of deletions.

Example 1

Input
s = "leEeetcode"
Output
leetcode
Explanation
Deleting "eE" leaves "leetcode".

Example 2

Input
s = "abBAcC"
Output
Explanation
Everything cancels out.

Example 3

Input
s = "s"
Output
s

Constraints

  • 1 <= s.length <= 40
  • s consists of upper and lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {string}
 */
var makeGood = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Make The String Great — Solution in Python, Java & C++

Make The String Great solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Make The String Great is an easy coding problem on strings and stack, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Strings, Stack
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A string is good if it contains no two adjacent characters s[i] and s[i+1] where one is the lowercase and the other the uppercase form of the same letter.

Repeatedly delete such a pair until the string is good, and return the result. The answer is unique regardless of the order of deletions.

Example 1

Input: s = "leEeetcode"
Output: leetcode
Explanation: Deleting "eE" leaves "leetcode".

Example 2

Input: s = "abBAcC"
Output: 
Explanation: Everything cancels out.

Example 3

Input: s = "s"
Output: s

Constraints

  • 1 <= s.length <= 40
  • s consists of upper and lowercase English letters.

Hints for Make The String Great

  1. Hint 1

    Push characters onto a stack one at a time.

  2. Hint 2

    Before pushing, check whether the character cancels the current top — same letter, different case.

  3. Hint 3

    Cancelling can expose a new pair underneath, which the stack handles automatically.

How to solve Make The String Great

Push characters onto a stack, cancelling when the incoming character is the same letter as the top in the opposite case.

Approach

  1. For each ch: if the stack top differs from ch but matches it case-insensitively, pop; otherwise push.
  2. Join the stack.

Why it works

Deleting a bad pair can expose a new bad pair around it, which the stack handles automatically since the top is always the most recent surviving character. The final string is unique, so any deletion order works.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • stack[-1] != ch is needed so aa is not treated as a bad pair.

Reference solution

Python

def makeGood(s: str) -> str:
    stack = []
    for ch in s:
        if stack and stack[-1] != ch and stack[-1].lower() == ch.lower():
            stack.pop()
        else:
            stack.append(ch)
    return "".join(stack)

Java

public static String makeGood(String s) {
    StringBuilder stack = new StringBuilder();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (stack.length() > 0) {
            char top = stack.charAt(stack.length() - 1);
            if (top != c && Character.toLowerCase(top) == Character.toLowerCase(c)) {
                stack.deleteCharAt(stack.length() - 1);
                continue;
            }
        }
        stack.append(c);
    }
    return stack.toString();
}

C++

string makeGood(string s) {
    string stk;
    for (char c : s) {
        if (!stk.empty()) {
            char top = stk.back();
            if (top != c && tolower(top) == tolower(c)) {
                stk.pop_back();
                continue;
            }
        }
        stk.push_back(c);
    }
    return stk;
}

JavaScript

var makeGood = function(s) {
    const stack = [];
    for (let i = 0; i < s.length; i++) {
        const c = s.charAt(i);
        if (stack.length > 0) {
            const top = stack[stack.length - 1];
            if (top !== c && top.toLowerCase() === c.toLowerCase()) {
                stack.pop();
                continue;
            }
        }
        stack.push(c);
    }
    return stack.join("");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Stack Data Structure