You are given a string s that consists of lowercase English letters.

You can perform the following operation any number of times (possibly zero times):

• Choose any letter that appears at least twice in the current string s and delete any one occurrence of that letter.

Your task is to return the lexicographically smallest string that can be formed by applying these operations.

In other words, you may repeatedly remove duplicate letters (only letters that currently appear two or more times can have one copy removed), and you want to arrange the deletions so that the final remaining string is as small as possible in dictionary order.

Key points to understand:

• A letter can only be deleted if it currently appears at least twice in the string. This means the last occurrence of any letter can never be removed, since once a letter has only one copy left, it must stay.
• The relative order of the remaining characters is preserved — deleting characters does not rearrange the string.
• "Lexicographically smallest" means that when comparing two possible results, we prefer the one that has a smaller character at the first position where they differ.

Example interpretation:

Suppose s = "bcabc". The letters b and c each appear twice, while a appears once. We could delete the first b and the first c to obtain "abc", which is the smallest possible result. Note that we cannot delete the only a, so a must remain in the output.

The goal is to decide, for each character that appears multiple times, whether removing an earlier occurrence allows a smaller character to take its place earlier in the string, thus producing a smaller overall result.

The core question we keep asking ourselves is: for each character, should we keep it where it is, or remove it because a smaller character can come earlier?

Let's think about what makes a string lexicographically smaller. When we compare strings from left to right, we want the smallest possible character as early as possible. So whenever we place a character, we'd love to know if some bigger character placed before it could be "pushed out" to let this smaller one move forward.

This leads to a natural greedy idea. Imagine building the result one character at a time. Suppose we have already placed some characters, and the most recent one we placed is larger than the new character c we are about to add. If that larger character still appears later in the string, then keeping it here is wasteful — we can delete it now (since it has a duplicate ahead, the deletion is allowed) and let the smaller character c take an earlier position. This is exactly the behavior of a monotonic stack.

The condition cnt[stk[-1]] > 1 is the key check. It tells us whether the character on top of the stack still has another occurrence somewhere later in the string. If it does, we are safe to pop it, because the operation rules require that a letter appears at least twice before we can remove one copy. If it appears only once, it is the last copy and must stay — so we stop popping.

So as we scan through s:

• We use cnt to track how many copies of each character are still "available" further along.
• Whenever the top of the stack is bigger than the current character and that top character has duplicates remaining, we pop it, decrement its count, and repeat. This greedily clears out larger characters that don't need to be where they are.
• Then we push the current character onto the stack.

After scanning everything, there's one more cleanup step. The string might end with characters that still have duplicates sitting in the stack — for example, a large character near the end that has earlier copies. Since these duplicates can be removed and doing so only shrinks the result (which makes a prefix-equal string smaller), we keep popping from the top while the top still has count greater than 1. This trims any remaining removable duplicates at the tail.

The reason this greedy strategy is correct is that the last occurrence of every distinct letter is untouchable — it can never be deleted. By keeping a non-decreasing-style stack and only ever removing characters that still have a copy ahead, we guarantee that every distinct letter survives at least once while pushing the smallest characters as far left as possible. The result naturally becomes the smallest arrangement achievable under the given deletion rules.

Pattern Learn more about Stack, Greedy and Monotonic Stack patterns.

Solution 1: Monotonic Stack

We use a stack stk to store the characters of the result string, and a hash table cnt to record the number of occurrences of each character in string s.

Step 1: Count occurrences.

First, we initialize cnt using a Counter to count how many times each character appears in string s. This count represents how many copies of each character are still "available" — and crucially, it lets us know whether a character has a duplicate that allows it to be safely deleted.

Step 2: Build the stack while scanning.

We iterate through each character c in string s and apply the following logic:

• While the stack is not empty, the top character of the stack is greater than c, and that top character still appears more than once (cnt[stk[-1]] > 1), we pop the top character and decrement its count in cnt. This greedily removes larger characters that don't need to stay where they are, allowing the smaller c to move earlier.
• After the popping loop finishes, we push c onto the stack.

The check cnt[stk[-1]] > 1 enforces the problem's rule that a letter must appear at least twice before one occurrence can be deleted. If the top character has only one copy left, it is the last occurrence and must remain, so we stop popping.

Step 3: Final cleanup of trailing duplicates.

After the scan, the stack may still contain characters that have duplicates. We continue popping the top character while cnt[stk[-1]] > 1, decrementing its count each time. Removing these trailing removable duplicates only shrinks the result, which makes it lexicographically smaller.

Step 4: Return the answer.

Finally, we join the characters in the stack with "".join(stk) to form the resulting string.

Walking through the code:

class Solution:
    def lexSmallestAfterDeletion(self, s: str) -> str:
        cnt = Counter(s)                      # count each character
        stk = []
        for c in s:
            while stk and stk[-1] > c and cnt[stk[-1]] > 1:
                cnt[stk.pop()] -= 1           # pop larger char with duplicates ahead
            stk.append(c)                     # push current char
        while stk and cnt[stk[-1]] > 1:
            cnt[stk.pop()] -= 1               # trim trailing removable duplicates
        return "".join(stk)

Complexity Analysis:

• Time complexity: O(n), where n is the length of string s. Each character is pushed onto the stack once and popped at most once, so the total work is linear.
• Space complexity: O(n) for the stack stk, plus O(|\Sigma|) for the hash table cnt, where |\Sigma| is the size of the character set (at most 26 for lowercase English letters).