Welcome to Subscribe On Youtube

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$.

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


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


  • 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)


  • 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)
}


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

All Problems

All Solutions