1081. Smallest Subsequence of Distinct Characters

Given a string s, return the lexicographically smallest subsequence of s that contains all the distinct characters of s exactly once.
 

Example 1:

Input: s = “bcabc”
Output: “abc”

Example 2:

Input: s = “cbacdcbc”
Output: “acdb”

Constraints:

• 1 <= s.length <= 1000
• s consists of lowercase English letters.

From: LeetCode
Link: 1081. Smallest Subsequence of Distinct Characters

Solution:

Ideas:

use a stack.
Remove bigger characters from the stack only if they appear again later.

Code:

char* smallestSubsequence(char* s) {
    int last[26];
    bool used[26] = {false};
    int n = strlen(s);

    for (int i = 0; i < n; i++) {
        last[s[i] - 'a'] = i;
    }

    char* stack = (char*)malloc(27 * sizeof(char));
    int top = 0;

    for (int i = 0; i < n; i++) {
        int c = s[i] - 'a';

        if (used[c]) continue;

        while (top > 0 &&
               stack[top - 1] > s[i] &&
               last[stack[top - 1] - 'a'] > i) {
            used[stack[top - 1] - 'a'] = false;
            top--;
        }

        stack[top++] = s[i];
        used[c] = true;
    }

    stack[top] = '\0';
    return stack;
}