# 3039. Apply Operations to Make String Empty

## Description

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 * 105
• s consists only of lowercase English letters.

## Solutions

### Solution 1

• 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();
}
}

• 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;
}
};

• 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)


• func lastNonEmptyString(s string) string {
cnt := [26]int{}
last := [26]int{}
mx := 0
for i, c := range s {
c -= 'a'
cnt[c]++
last[c] = i
mx = max(mx, cnt[c])
}
ans := []rune{}
for i, c := range s {
if cnt[c-'a'] == mx && last[c-'a'] == i {
ans = append(ans, c)
}
}
return string(ans)
}

• function lastNonEmptyString(s: string): string {
const cnt: number[] = Array(26).fill(0);
const last: number[] = Array(26).fill(0);
const n = s.length;
let mx = 0;
for (let i = 0; i < n; ++i) {
const c = s.charCodeAt(i) - 97;
mx = Math.max(mx, ++cnt[c]);
last[c] = i;
}
const ans: string[] = [];
for (let i = 0; i < n; ++i) {
const c = s.charCodeAt(i) - 97;
if (cnt[c] === mx && last[c] === i) {
ans.push(String.fromCharCode(c + 97));
}
}
return ans.join('');
}