Question

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: Hash Table or Array

We use a hash table or array $cnt$ to record the occurrence times of each character in string $s$, and use another hash table or array $last$ to record the last occurrence position of each character in string $s$. The maximum occurrence times of characters in string $s$ is denoted as $mx$.

Then we traverse the string $s$. If the occurrence times of the current character equals $mx$ and the position of the current character equals the last occurrence position of this character, then we add the current character to the answer.

After the traversal, we return the answer.

The time complexity is $O(n)$, and the space complexity is $O(|\Sigma|)$, where $n$ is the length of string $s$, and $\Sigma$ is the character set. In this problem, $\Sigma$ is the set of lowercase English letters.

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)

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

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