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 strings rightbefore applying the last operation. In the example above, answer is "ba".

Examples

Example 1

1
2
3

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

Example 2

1
2
3
4
5

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

Solution

Method 1 – Simulation with Last Occurrence Tracking

Intuition

The key idea is to simulate the process: in each round, remove the first occurrence of every character from ‘a’ to ‘z’. The string just before the last operation is the set of characters that will be removed in the final round. These are the characters that appear last in the string (i.e., their last occurrence). By collecting the characters at their last occurrence positions in order, we can construct the answer efficiently.

Approach

  1. Traverse the string and record the last index of each character.
  2. Iterate through the string again, and for each character, if its index matches its last occurrence, add it to the answer.
  3. Concatenate these characters in their original order to form the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
  string lastNonEmptyString(string s) {
    vector<int> last(26, -1);
    int n = s.size();
    for (int i = 0; i < n; ++i)
      last[s[i] - 'a'] = i;
    string ans;
    for (int i = 0; i < n; ++i)
      if (last[s[i] - 'a'] == i)
        ans += s[i];
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
  public String lastNonEmptyString(String s) {
    int[] last = new int[26];
    int n = s.length();
    for (int i = 0; i < 26; ++i) last[i] = -1;
    for (int i = 0; i < n; ++i)
      last[s.charAt(i) - 'a'] = i;
    StringBuilder ans = new StringBuilder();
    for (int i = 0; i < n; ++i)
      if (last[s.charAt(i) - 'a'] == i)
        ans.append(s.charAt(i));
    return ans.toString();
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
  def lastNonEmptyString(self, s: str) -> str:
    last: dict[str, int] = {}
    n: int = len(s)
    for i, c in enumerate(s):
      last[c] = i
    ans: list[str] = []
    for i, c in enumerate(s):
      if last[c] == i:
        ans.append(c)
    return ''.join(ans)

Complexity

  • ⏰ Time complexity: O(N), where N is the length of the string.
  • 🧺 Space complexity: O(1) (since there are only 26 lowercase letters).