# Apply Operations to Make String Empty
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/apply-operations-to-make-string-empty)
Canonical: https://scaleengineer.com/dsa/problems/apply-operations-to-make-string-empty
**Patterns:** [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [Virtusa](https://scaleengineer.com/companies/virtusa)
---
## 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 = "**a**a**bc**bbca"`. The resulting string is `s = "abbca"`.
* Remove the underlined characters `s = "**ab**b**c**a"`. 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 * 105`
* `s` consists only of lowercase English letters.

# Approaches
## Brute-Force Simulation
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public String applyOperations(String s) {
        String result = "";
        while (!s.isEmpty()) {
            result = s;
            StringBuilder nextS = new StringBuilder();
            boolean[] seen = new boolean[26];
            for (char c : s.toCharArray()) {
                int charIndex = c - 'a';
                if (!seen[charIndex]) {
                    seen[charIndex] = true;
                } else {
                    nextS.append(c);
                }
            }
            s = nextS.toString();
        }
        return 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`.

## Single-Pass Frequency and Last Index Counting
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.
**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.
**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.
### Explanation
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.

```java
import java.util.*;

class Solution {
    // Helper class to store character and its last index
    private static class CharInfo {
        char character;
        int index;
        
        CharInfo(char character, int index) {
            this.character = character;
            this.index = index;
        }
    }

    public String applyOperations(String s) {
        int[] freq = new int[26];
        int[] lastIndex = new int[26];
        
        // Single pass to compute frequencies and last indices
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            freq[c - 'a']++;
            lastIndex[c - 'a'] = i;
        }
        
        // Find the maximum frequency
        int maxFreq = 0;
        for (int count : freq) {
            if (count > maxFreq) {
                maxFreq = count;
            }
        }
        
        // Collect characters with maximum frequency
        List<CharInfo> candidates = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            if (freq[i] == maxFreq) {
                candidates.add(new CharInfo((char)('a' + i), lastIndex[i]));
            }
        }
        
        // Sort candidates by their last index
        Collections.sort(candidates, Comparator.comparingInt(a -> a.index));
        
        // Build the result string
        StringBuilder result = new StringBuilder();
        for (CharInfo ci : candidates) {
            result.append(ci.character);
        }
        
        return result.toString();
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
public
  String lastNonEmptyString(String s) {
    int[] cnt = new int[26];
    int[] last = new int[26];
    int n = s.length();
    int mx = 0;
    for (int i = 0; i < n; ++i) {
      int c = s.charAt(i) - 'a';
      mx = Math.max(mx, ++cnt[c]);
      last[c] = i;
    }
    StringBuilder ans = new StringBuilder();
    for (int i = 0; i < n; ++i) {
      int c = s.charAt(i) - 'a';
      if (cnt[c] == mx && last[c] == i) {
        ans.append(s.charAt(i));
      }
    }
    return ans.toString();
  }
}

```

### CPP

```cpp
class Solution {
public:
  string lastNonEmptyString(string s) {
    int cnt[26]{};
    int last[26]{};
    int n = s.size();
    int mx = 0;
    for (int i = 0; i < n; ++i) {
      int c = s[i] - 'a';
      mx = max(mx, ++cnt[c]);
      last[c] = i;
    }
    string ans;
    for (int i = 0; i < n; ++i) {
      int c = s[i] - 'a';
      if (cnt[c] == mx && last[c] == i) {
        ans.push_back(s[i]);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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)

```