Apply Operations to Make String Empty - Practice Coding Problems

Apply Operations to Make String Empty - Problem

You are given a string s. Consider performing the following operation until s becomes empty:

For every alphabet character from 'a' to 'z', remove the first occurrence of that character in s (if it exists).

For example, let initially s = "aabcbbca". We do the following operations:

Remove the underlined characters s = "aabcbbca". The resulting string is s = "abbca".
Remove the underlined characters s = "abbca". The resulting string is s = "ba".
Remove the underlined characters s = "ba". The resulting string is s = "".

Return the value of the string s right before applying the last operation. In the example above, answer is "ba".

Input & Output

Example 1 — Basic Case

$ Input: s = "aabcbbca"

› Output: "ab"

💡 Note: After round 1: remove first 'a', 'b', 'c' → "abbca". After round 2: remove first 'a', 'b', 'c' → "ba". After round 3: remove first 'a', 'b' → "". Return "ba" from before the last operation, but we need to reconsider... Actually, characters 'a' and 'b' both appear 3 times (max frequency), so they form the final non-empty string in order: "ab".

Example 2 — Single Character

$ Input: s = "abcd"

› Output: ""

💡 Note: All characters appear once. After first round, all are removed and string becomes empty. The string before last operation is empty.

Example 3 — Repeated Pattern

$ Input: s = "aaaa"

› Output: "a"

💡 Note: Character 'a' appears 4 times. Each round removes one 'a', so we get: "aaaa" → "aaa" → "aa" → "a" → "". Return "a" from before the last operation.

Constraints

1 ≤ s.length ≤ 5 × 10⁴
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

Original string with character frequencies

Process

Find characters with maximum frequency

Output

String formed by max frequency characters

Key Takeaway

🎯 Key Insight: Characters with maximum frequency survive the longest and form the final non-empty string

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that characters with maximum frequency will be the last ones remaining before the string becomes empty. We can solve this efficiently by counting character frequencies in O(n) time instead of simulating the removal process. Best approach is frequency counting: Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Counting Approach	O(n)	O(1)	Calculate character frequencies and determine which survive to the final round
Simulation Approach	O(n² × 26)	O(n)	Simulate the removal process step by step until string becomes empty

Frequency Counting Approach — Algorithm Steps

Count frequency of each character
Find maximum frequency (number of rounds)
Collect characters that appear exactly max_freq times
Return string formed by these characters in original order

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Count how many times each character appears

Find Maximum

Find the highest frequency count

Build Result

Collect characters with maximum frequency in order

Code -

solution.c — C

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

char* solution(char* s) {
    int len = strlen(s);
    if (len == 0) {
        char* result = malloc(1);
        result[0] = '\0';
        return result;
    }
    
    // Count frequency of each character
    int freq[256] = {0};
    for (int i = 0; s[i]; i++) {
        freq[(unsigned char)s[i]]++;
    }
    
    // Find maximum frequency
    int maxFreq = 0;
    for (int i = 0; i < 256; i++) {
        if (freq[i] > maxFreq) {
            maxFreq = freq[i];
        }
    }
    
    // If max frequency is 1, return empty string
    if (maxFreq == 1) {
        char* result = malloc(1);
        result[0] = '\0';
        return result;
    }
    
    // Build result with characters that have max frequency
    char* result = malloc((len + 1) * sizeof(char));
    bool seen[256] = {false};
    int resultLen = 0;
    
    for (int i = 0; s[i]; i++) {
        unsigned char c = (unsigned char)s[i];
        if (freq[c] == maxFreq && !seen[c]) {
            result[resultLen++] = s[i];
            seen[c] = true;
        }
    }
    
    result[resultLen] = '\0';
    return result;
}

int main() {
    char s[100001];
    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 to count frequencies and another pass to build result

✓ Linear Growth

Space Complexity

O(1)

Only need frequency array for 26 characters (constant space)

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

890 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

Frequency Counting Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler