Apply Operations to Make String Empty

Med

#2707Time: O(N * K), where N is the initial length of the string and K is the number of operations. In the worst case (e.g., `s = "aaaaa..."`), K can be O(N), leading to a time complexity of O(N^2).Space: O(N), where N is the length of the input string. This is because in each step, a new string (or `StringBuilder`) of a length up to N is created.1 company

Patterns

Algorithms

Data structures

Companies

Prompt

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".

Example 1:

Input: s = "aabcbbca"
Output: "ba"
Explanation: Explained in the statement.

Example 2:

Input: s = "abcd"
Output: "abcd"
Explanation: We do the following operation:
- Remove the underlined characters s = "abcd". The resulting string is s = "".
The string just before the last operation is "abcd".

Constraints:

1 <= s.length <= 5 * 10⁵
s consists only of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. It repeatedly applies the operation on the string until it becomes empty. In each step, it identifies the first occurrence of every unique character present in the string, removes them to form a new string, and then proceeds to the next step with this new string. The string from the step just before the string becomes empty is stored and returned as the result.

Algorithm

Initialize an empty string result to store the string state before each operation.
Enter a loop that continues as long as the current string s is not empty.
Inside the loop, first assign the current value of s to result.
Create a StringBuilder to build the string for the next iteration.
Use a boolean array seen of size 26, initialized to false, to track which characters ('a' through 'z') have had their first occurrence removed in the current operation.
Iterate through each character c of the current string s:
- If c has not been seen yet (i.e., seen[c - 'a'] is false), mark it as seen and do not append it to the StringBuilder. This effectively removes its first occurrence.
- If c has already been seen, append it to the StringBuilder.
After the iteration, update s to the string constructed by the StringBuilder.
Once the loop terminates (when s becomes empty), return the value stored in result.

Walkthrough

The algorithm maintains the string s and a variable result to store the state of s before an operation. It enters a while loop that continues as long as s is not empty. Inside the loop, the current s is saved to result. A boolean array seen of size 26 is used to track which characters have had their first occurrence removed in the current operation. A StringBuilder is used to construct the string for the next iteration. We iterate through the characters of the current string s. For each character c, if it's the first time we're seeing it in this iteration, we mark it as seen and skip it. Otherwise, we append it to the StringBuilder. After iterating through s, the StringBuilder contains the string for the next operation. We update s to this new string. The loop continues until s is empty. The final value stored in result is the answer.

1class Solution {2    public String applyOperations(String s) {3        String result = "";4        while (!s.isEmpty()) {5            result = s;6            StringBuilder nextS = new StringBuilder();7            boolean[] seen = new boolean[26];8            for (char c : s.toCharArray()) {9                int charIndex = c - 'a';10                if (!seen[charIndex]) {11                    seen[charIndex] = true;12                } else {13                    nextS.append(c);14                }15            }16            s = nextS.toString();17        }18        return result;19    }20}

Complexity

Time

O(N * K), where N is the initial length of the string and K is the number of operations. In the worst case (e.g., `s = "aaaaa..."`), K can be O(N), leading to a time complexity of O(N^2).

Space

O(N), where N is the length of the input string. This is because in each step, a new string (or `StringBuilder`) of a length up to N is created.

Trade-offs

Pros

Simple to understand and implement as it directly follows the problem description.
It is a good starting point for understanding the problem mechanics.

Cons

Highly inefficient for large inputs due to its quadratic time complexity in the worst case.
Repeatedly creates new string objects or manipulates a StringBuilder, which can be slow and memory-intensive.
Likely to result in a 'Time Limit Exceeded' error on platforms with strict time constraints for the given input size.

This optimal approach avoids the costly simulation by making a key observation about the process. The total number of operations is determined by the character with the highest frequency. The characters that are removed in the very last operation are precisely those that had this maximum frequency. Therefore, the problem reduces to finding these characters and arranging them in the order of their final appearance in the original string.

Algorithm

Step 1: Count Frequencies and Last Indices.
- Create an integer array freq of size 26 to store character counts and another integer array lastIndex of size 26 to store the last seen index of each character.
- Iterate through the input string s once from left to right. For each character, increment its count in freq and update its last seen index in lastIndex.
Step 2: Find Maximum Frequency.
- Scan the freq array to find the maximum frequency, max_freq.
Step 3: Collect Candidate Characters.
- Create a list to store candidate objects/pairs.
- Iterate from 'a' to 'z'. If a character's frequency in the freq array equals max_freq, add a new object containing this character and its last index (from lastIndex) to the list.
Step 4: Sort Candidates.
- Sort the list of candidates in ascending order based on their last indices.
Step 5: Build and Return Result.
- Create a StringBuilder.
- Iterate through the sorted list of candidates and append each character to the StringBuilder.
- Return the final string from the StringBuilder.

Walkthrough

The core idea is to find all characters that appear most frequently and then arrange them based on their last occurrence in the original string. This can be done efficiently in a single pass.

First, we iterate through the input string s to populate two arrays of size 26: one for character frequencies (freq) and one for the last seen index of each character (lastIndex). After this single pass, we find the maximum frequency (max_freq) from the freq array. Then, we identify all characters that have a frequency equal to max_freq. For each of these characters, we retrieve their last known index. We collect these (character, last_index) pairs and sort them based on the index. This sorting step ensures that the characters are in the correct final order. Finally, we construct the result string by concatenating the characters from the sorted list.

1import java.util.*;2 3class Solution {4    // Helper class to store character and its last index5    private static class CharInfo {6        char character;7        int index;8        9        CharInfo(char character, int index) {10            this.character = character;11            this.index = index;12        }13    }14 15    public String applyOperations(String s) {16        int[] freq = new int[26];17        int[] lastIndex = new int[26];18        19        // Single pass to compute frequencies and last indices20        for (int i = 0; i < s.length(); i++) {21            char c = s.charAt(i);22            freq[c - 'a']++;23            lastIndex[c - 'a'] = i;24        }25        26        // Find the maximum frequency27        int maxFreq = 0;28        for (int count : freq) {29            if (count > maxFreq) {30                maxFreq = count;31            }32        }33        34        // Collect characters with maximum frequency35        List<CharInfo> candidates = new ArrayList<>();36        for (int i = 0; i < 26; i++) {37            if (freq[i] == maxFreq) {38                candidates.add(new CharInfo((char)('a' + i), lastIndex[i]));39            }40        }41        42        // Sort candidates by their last index43        Collections.sort(candidates, Comparator.comparingInt(a -> a.index));44        45        // Build the result string46        StringBuilder result = new StringBuilder();47        for (CharInfo ci : candidates) {48            result.append(ci.character);49        }50        51        return result.toString();52    }53}

Complexity

Time

O(N), where N is the length of the string. The initial pass to calculate frequencies and last indices takes O(N). All subsequent steps (finding max frequency, collecting candidates, sorting, and building the string) take constant time because the alphabet size is fixed at 26.

Space

O(1). We use a few arrays of size 26 and a list that can hold at most 26 elements. The space required is constant and does not depend on the input string length N.

Trade-offs

Pros

Extremely efficient with a linear time complexity, making it suitable for large inputs.
Uses constant extra space, as the storage for frequencies, indices, and candidates does not depend on the input string's length.
Solves the problem with a single pass over the string, avoiding repeated and costly string manipulations.

Cons

Requires a logical leap to connect character frequencies to the final state, making it less intuitive than a direct simulation.
The implementation is slightly more complex, involving helper data structures to store and sort character information.

Solutions

Solution

1class Solution {2public3  String lastNonEmptyString(String s) {4    int[] cnt = new int[26];5    int[] last = new int[26];6    int n = s.length();7    int mx = 0;8    for (int i = 0; i < n; ++i) {9      int c = s.charAt(i) - 'a';10      mx = Math.max(mx, ++cnt[c]);11      last[c] = i;12    }13    StringBuilder ans = new StringBuilder();14    for (int i = 0; i < n; ++i) {15      int c = s.charAt(i) - 'a';16      if (cnt[c] == mx && last[c] == i) {17        ans.append(s.charAt(i));18      }19    }20    return ans.toString();21  }22}

1class Solution {2public:3  string lastNonEmptyString(string s) {4    int cnt[26]{};5    int last[26]{};6    int n = s.size();7    int mx = 0;8    for (int i = 0; i < n; ++i) {9      int c = s[i] - 'a';10      mx = max(mx, ++cnt[c]);11      last[c] = i;12    }13    string ans;14    for (int i = 0; i < n; ++i) {15      int c = s[i] - 'a';16      if (cnt[c] == mx && last[c] == i) {17        ans.push_back(s[i]);18      }19    }20    return ans;21  }22};

1class Solution:2    def lastNonEmptyString(self, s: str) -> str: cnt = Counter(s) mx = cnt . most_common(1)[0][1] last = {c: i for i, c in enumerate(s)} return "" . join(c for i, c in enumerate(s) if cnt[c] == mx and last[c] == i)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem