1081. Smallest Subsequence of Distinct Characters

Problem

Tags: String, Stack, Greedy, Monotonic Stack

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.

Note: This question is the same as 316: https://leetcode.com/problems/remove-duplicate-letters/

Code

C

// 1081. Smallest Subsequence of Distinct Characters (9/11/54180)
// Runtime: 0 ms (75.00%) Memory: 5.52 MB (75.00%) 

char* smallestSubsequence (char* s) {
    int last_pos[26] = { -1 };
    for (int i = 0; s[i] != '\0'; i++) {
        last_pos[s[i] - 'a'] = i;
    }
    
    bool used[26] = { false };
    int stk[1001] = { 0 };
    int stk_size = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        int code = s[i] - 'a';
        if (used[code]) {
            continue;
        }
        
        while (stk_size) {
            int prev = stk[stk_size - 1];
            if (prev < code || i >= last_pos[prev]) {
                break;
            }
            stk_size--;
            used[prev] = false;
        }
        
        stk[stk_size++] = code;
        used[code] = true;
    }
    
    char* ans = (char*)calloc(stk_size + 1, sizeof(char));
    for (int i = 0; i < stk_size; i++) {
        ans[i] = stk[i] + 'a';
    }
    
    return ans;
}