Problem Description

You are given a string s consisting of lowercase English letters.

You need to repeatedly perform the following operation until the string becomes empty:

• For every alphabet character from 'a' to 'z', remove the first occurrence of that character in s (if it exists).

This means in each operation, you scan through the alphabet from 'a' to 'z' and remove the first occurrence of each letter that appears in the string.

For example, with s = "aabcbbca":

• First operation: Remove the first 'a' at position 0, first 'b' at position 3, and first 'c' at position 4. The string becomes "abbca".
• Second operation: Remove the first 'a' at position 0, first 'b' at position 1, and first 'c' at position 3. The string becomes "ba".
• Third operation: Remove the first 'a' at position 1 and first 'b' at position 0. The string becomes "" (empty).

Your task is to return the value of the string s right before applying the last operation that makes it empty. In the example above, the answer would be "ba" since that's the string before the final operation that empties it.

The key insight is that characters appearing more frequently in the original string will survive longer through the operations. The characters that appear the maximum number of times will be the ones remaining in the string right before it becomes empty. Among these characters, their relative order in the final string corresponds to their last occurrence positions in the original string.

Intuition

Let's think about what happens during each operation. We remove one occurrence of each unique character that exists in the string. This means that if a character appears n times in the original string, it will take exactly n operations to completely remove all occurrences of that character.

Consider which characters will be present in the string right before the final operation. Since each operation removes one occurrence of each existing character, the characters that survive the longest are those with the maximum frequency. If the maximum frequency is mx, then after mx - 1 operations, only the characters with frequency mx will remain (each having exactly one occurrence left).

For example, if we have s = "aabcbbca":

• 'a' appears 3 times
• 'b' appears 3 times
• 'c' appears 2 times

After 2 operations, 'c' is completely removed, but 'a' and 'b' each have one occurrence remaining.

Now, which specific occurrences of these maximum-frequency characters survive? During each operation, we always remove the first occurrence of each character. This means the last occurrence of each character in the original string will be the one that survives the longest.

Therefore, the string right before the final operation consists of:

1. Only the characters that appear with maximum frequency mx
2. Specifically, the last occurrence of each such character in the original string
3. These characters appear in their original relative order

To implement this, we need to:

• Count the frequency of each character to find mx
• Track the last position of each character in the original string
• Build the result by including characters where both conditions are met: the character has maximum frequency AND we're at its last occurrence position

Learn more about Sorting patterns.

Solution Approach

The solution uses hash tables to efficiently track character frequencies and positions:

1. Count character frequencies: Use a Counter (hash table) to count how many times each character appears in the string s. Store this in cnt.

2. Find maximum frequency: Determine the maximum frequency mx among all characters. This can be done using cnt.most_common(1)[0][1], which returns the count of the most frequent character.

3. Track last positions: Create a dictionary last where last[c] stores the index of the last occurrence of character c in the string. We iterate through the string with enumerate(s) and continuously update last[c] = i for each character. Since we process left to right, the final value will be the rightmost position.

4. Build the result string: Iterate through the string one more time with index i and character c. For each position, check if:

   • The character c has maximum frequency: cnt[c] == mx
   • The current position is the last occurrence of this character: last[c] == i

   If both conditions are met, include this character in the result.

5. Return the result: Join all selected characters to form the final string using "".join().

The time complexity is O(n) where n is the length of the string, as we make a few passes through the string. The space complexity is O(1) for the hash tables since we're limited to 26 lowercase letters, making the space usage constant regardless of input size.

This approach elegantly identifies exactly which characters and which specific occurrences form the string right before it becomes empty, without actually simulating all the removal operations.

Example Walkthrough

Let's walk through the solution with s = "abacaba".

Step 1: Count character frequencies

• 'a' appears 4 times
• 'b' appears 2 times
• 'c' appears 1 time

Step 2: Find maximum frequency

• mx = 4 (the frequency of 'a')

Step 3: Track last positions Going through the string "abacaba" from left to right:

• Index 0: 'a' → last['a'] = 0
• Index 1: 'b' → last['b'] = 1
• Index 2: 'a' → last['a'] = 2
• Index 3: 'c' → last['c'] = 3
• Index 4: 'a' → last['a'] = 4
• Index 5: 'b' → last['b'] = 5
• Index 6: 'a' → last['a'] = 6

Final last positions: last = {'a': 6, 'b': 5, 'c': 3}

Step 4: Build the result string Now iterate through the string again and check each position:

• Index 0: 'a', frequency is 4 (= mx), but last position is 6 (≠ 0) → skip
• Index 1: 'b', frequency is 2 (≠ mx) → skip
• Index 2: 'a', frequency is 4 (= mx), but last position is 6 (≠ 2) → skip
• Index 3: 'c', frequency is 1 (≠ mx) → skip
• Index 4: 'a', frequency is 4 (= mx), but last position is 6 (≠ 4) → skip
• Index 5: 'b', frequency is 2 (≠ mx) → skip
• Index 6: 'a', frequency is 4 (= mx), and last position is 6 (= 6) → include 'a'

Result: "a"

This makes sense because after 3 operations:

• Operation 1: Remove first 'a', 'b', 'c' → "aaba"
• Operation 2: Remove first 'a', 'b' → "aa"
• Operation 3: Remove first 'a' → "a"
• Operation 4: Remove first 'a' → "" (empty)

The string right before the last operation is indeed "a".

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of string s. This is because:

• Creating the Counter takes O(n) time as it iterates through all characters in s
• Finding the most common element using most_common(1) takes O(|Σ|) time where |Σ| is the size of the character set (26 lowercase letters), which is effectively O(1)
• Building the last dictionary takes O(n) time as it iterates through all characters in s
• The final list comprehension iterates through s once more with O(1) lookups for cnt[c] and last[c], taking O(n) time
• The join operation takes O(k) where k is the length of the result string, and k ≤ n

Overall: O(n) + O(1) + O(n) + O(n) = O(n)

The space complexity is O(|Σ|), where |Σ| is the character set size (26 lowercase English letters). This is because:

• The Counter cnt stores at most |Σ| unique characters and their counts, taking O(|Σ|) space
• The last dictionary also stores at most |Σ| unique characters and their last indices, taking O(|Σ|) space
• The output string takes O(k) space where k ≤ |Σ| (at most one occurrence of each character with maximum frequency)

Overall: O(|Σ|) + O(|Σ|) + O(|Σ|) = O(|Σ|)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding Character Selection Logic

The Problem: A common mistake is thinking that we need ALL occurrences of characters with maximum frequency, rather than just their LAST occurrences. This leads to incorrect results.

Incorrect Approach:

# WRONG: This includes all occurrences of max-frequency characters
result = "".join(char for char in s if char_count[char] == max_frequency)

Why It's Wrong: If s = "aabcbbca", where 'a' and 'b' appear 3 times (max frequency), this would return "aabbba" instead of the correct "ba".

Correct Fix: Only include characters at their last occurrence position:

result = "".join(
    char for index, char in enumerate(s) 
    if char_count[char] == max_frequency and last_occurrence[char] == index
)

Pitfall 2: Dictionary Comprehension Overwrites Earlier Positions

The Problem: Using dictionary comprehension to find last occurrences works correctly, but beginners might try to find first occurrences and get confused:

# Attempting to find first occurrences (WRONG for this problem)
first_occurrence = {}
for i, c in enumerate(s):
    if c not in first_occurrence:
        first_occurrence[c] = i

Why It Matters: The problem requires the LAST occurrences of max-frequency characters to maintain proper ordering. Using first occurrences would give the wrong relative positions.

Correct Approach: The dictionary comprehension {char: index for index, char in enumerate(s)} naturally keeps the last occurrence because later iterations overwrite earlier values.

Pitfall 3: Forgetting Edge Cases

The Problem: Not handling edge cases like single-character strings or strings where all characters appear exactly once.

Example Edge Cases:

• s = "a" → Should return "a"
• s = "abcdef" → All characters have frequency 1, should return "abcdef"

Solution: The current implementation handles these correctly, but it's important to verify:

# Test with edge cases
assert Solution().lastNonEmptyString("a") == "a"
assert Solution().lastNonEmptyString("abc") == "abc"

Pitfall 4: Inefficient Maximum Frequency Calculation

The Problem: Some might iterate through all values to find the maximum:

# Less efficient approach
max_frequency = max(char_count.values())

Why the Given Solution is Better: Using char_count.most_common(1)[0][1] is more idiomatic and potentially more efficient for Counter objects, though both work correctly.

Alternative Correct Approach: If you prefer explicit max finding:

max_frequency = max(char_count.values()) if char_count else 0