Make The String Great - Practice Coding Problems

Make The String Great - Problem

String Stack Easy

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.

Input & Output

Example 1 — Basic Removal

$ Input: s = "leEeetcode"

› Output: "leetcode"

💡 Note: Remove the 'eE' pair: 'e' and 'E' are the same letter but different cases, so we remove both. Result: "leetcode"

Example 2 — Multiple Removals

$ Input: s = "abBAcC"

› Output: ""

💡 Note: Remove 'bB' → "aAcC", then remove 'cC' → "aA", finally remove 'aA' → "". Result: empty string

Example 3 — No Removals Needed

$ Input: s = "s"

› Output: "s"

💡 Note: Single character has no adjacent pairs to remove. Result: "s"

Constraints

1 ≤ s.length ≤ 100
s contains only lowercase and uppercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input String

String with potential bad pairs (same letter, different cases)

Remove Bad Pairs

Eliminate adjacent characters that are same letter but different cases

Good String

Final string with no bad pairs remaining

Key Takeaway

🎯 Key Insight: Use a stack to efficiently handle cascading removals when characters cancel each other out

Asked in

f Facebook 15 a Amazon 12

The key insight is to use a stack to efficiently handle cascading character removals. When we encounter a character that forms a bad pair with the stack top (same letter, different case), we pop the stack instead of pushing. Best approach is the stack solution with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Stack-Based Solution	O(n)	O(n)	Use a stack to build result, popping when we find conflicting pairs
Repeated Scanning	O(n²)	O(n)	Repeatedly scan the string and remove one bad pair at a time

Stack-Based Solution — Algorithm Steps

Step 1: Process each character in the string
Step 2: If it forms bad pair with stack top, pop the stack
Step 3: Otherwise, push character to stack
Step 4: Convert stack to final string

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Characters

Iterate through each character

Check for Pairs

Compare with stack top

Build Result

Push or pop based on comparison

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

char* solution(char* s) {
    int len = strlen(s);
    char* stack = (char*)malloc((len + 1) * sizeof(char));
    int top = -1;
    
    for (int i = 0; i < len; i++) {
        char c = s[i];
        if (top >= 0 && stack[top] != c && tolower(stack[top]) == tolower(c)) {
            // Found a bad pair, remove from stack
            top--;
        } else {
            // Add character to stack
            stack[++top] = c;
        }
    }
    
    stack[top + 1] = '\0';
    return stack;
}

int main() {
    char s[1001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string, each character processed once

✓ Linear Growth

Space Complexity

O(n)

Stack can hold up to n characters in worst case

⚡ Linearithmic Space

94.0K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack-Based Solution — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler