Skip to content

3816. Lexicographically Smallest String After Deleting Duplicate Characters

Description

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.

Return the lexicographically smallest resulting string that can be formed this way.

Β 

Example 1:

Input: s = "aaccb"

Output: "aacb"

Explanation:

We can form the strings "acb", "aacb", "accb", and "aaccb". "aacb" is the lexicographically smallest one.

For example, we can obtain "aacb" by choosing 'c' and deleting its first occurrence.

Example 2:

Input: s = "z"

Output: "z"

Explanation:

We cannot perform any operations. The only string we can form is "z".

Β 

Constraints:

  • 1 <= s.length <= 105
  • s contains lowercase English letters only.

Solutions

Solution 1: Monotonic Stack

We can use a stack \(\textit{stk}\) to store the characters of the result string, and a hash table \(\textit{cnt}\) to record the number of occurrences of each character in string \(s\).

First, we initialize \(\textit{cnt}\) to count the occurrences of each character in string \(s\). Then, we iterate through each character \(c\) in string \(s\):

  • If the stack is not empty, the top character of the stack is greater than \(c\), and the top character will appear again in string \(s\), we pop the top character and decrement its count in \(\textit{cnt}\).
  • Push character \(c\) into the stack.

Finally, if there are duplicate characters in the stack, we continue to pop the top character until the count of the top character in \(\textit{cnt}\) is 1.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the string \(s\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def lexSmallestAfterDeletion(self, s: str) -> str:
        cnt = Counter(s)
        stk = []
        for c in s:
            while stk and stk[-1] > c and cnt[stk[-1]] > 1:
                cnt[stk.pop()] -= 1
            stk.append(c)
        while stk and cnt[stk[-1]] > 1:
            cnt[stk.pop()] -= 1
        return "".join(stk)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public String lexSmallestAfterDeletion(String s) {
        int[] cnt = new int[26];
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            ++cnt[s.charAt(i) - 'a'];
        }
        StringBuilder stk = new StringBuilder();
        for (int i = 0; i < n; ++i) {
            char c = s.charAt(i);
            while (stk.length() > 0 && stk.charAt(stk.length() - 1) > c
                && cnt[stk.charAt(stk.length() - 1) - 'a'] > 1) {
                --cnt[stk.charAt(stk.length() - 1) - 'a'];
                stk.setLength(stk.length() - 1);
            }
            stk.append(c);
        }
        while (cnt[stk.charAt(stk.length() - 1) - 'a'] > 1) {
            --cnt[stk.charAt(stk.length() - 1) - 'a'];
            stk.setLength(stk.length() - 1);
        }
        return stk.toString();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    string lexSmallestAfterDeletion(string s) {
        int cnt[26]{};
        for (char c : s) {
            ++cnt[c - 'a'];
        }
        string stk;
        for (char c : s) {
            while (stk.size() && stk.back() > c && cnt[stk.back() - 'a'] > 1) {
                --cnt[stk.back() - 'a'];
                stk.pop_back();
            }
            stk.push_back(c);
        }
        while (cnt[stk.back() - 'a'] > 1) {
            --cnt[stk.back() - 'a'];
            stk.pop_back();
        }
        return stk;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func lexSmallestAfterDeletion(s string) string {
    cnt := [26]int{}
    for _, c := range s {
        cnt[c-'a']++
    }
    stk := []byte{}
    for _, c := range s {
        for len(stk) > 0 && stk[len(stk)-1] > byte(c) && cnt[stk[len(stk)-1]-'a'] > 1 {
            cnt[stk[len(stk)-1]-'a']--
            stk = stk[:len(stk)-1]
        }
        stk = append(stk, byte(c))
    }
    for cnt[stk[len(stk)-1]-'a'] > 1 {
        cnt[stk[len(stk)-1]-'a']--
        stk = stk[:len(stk)-1]
    }
    return string(stk)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function lexSmallestAfterDeletion(s: string): string {
    const cnt: number[] = new Array(26).fill(0);
    const n = s.length;
    const a = 'a'.charCodeAt(0);
    for (let i = 0; i < n; ++i) {
        ++cnt[s.charCodeAt(i) - a];
    }
    const stk: string[] = [];
    for (let i = 0; i < n; ++i) {
        const c = s[i];
        while (
            stk.length > 0 &&
            stk[stk.length - 1] > c &&
            cnt[stk[stk.length - 1].charCodeAt(0) - a] > 1
        ) {
            --cnt[stk.pop()!.charCodeAt(0) - a];
        }
        stk.push(c);
    }
    while (cnt[stk[stk.length - 1].charCodeAt(0) - a] > 1) {
        --cnt[stk.pop()!.charCodeAt(0) - a];
    }
    return stk.join('');
}

Comments