LeetCode //C - 316. Remove Duplicate Letters

316. Remove Duplicate Letters

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
 

Example 1:

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

Example 2:

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

Constraints:

• $1<=s.length<=10^4$
• s consists of lowercase English letters.

From: LeetCode
Link: 316. Remove Duplicate Letters

---

Solution:

Ideas:

1. lastIndex[]: This array stores the last occurrence of each character in the input string s.

2. seen[]: This boolean array keeps track of which characters are already included in the stack (result).

3. stack: This array is used as a stack to build the result string with the smallest lexicographical order.

4. Algorithm:

• Traverse through each character in the string s.
• Skip the character if it is already in the result.
• Otherwise, pop characters from the stack if they are lexicographically greater than the current character and if they appear later in the string.
• Push the current character onto the stack and mark it as seen.

5. The final stack contains the result, which is then null-terminated and returned as the result string.

Code:

char* removeDuplicateLetters(char* s) {
    int len = strlen(s);
    int lastIndex[26] = {0};  // To store the last occurrence of each character
    bool seen[26] = {false};  // To keep track of seen characters
    int stackSize = 0;        // To keep track of stack size
    
    // Find the last occurrence of each character
    for (int i = 0; i < len; i++) {
        lastIndex[s[i] - 'a'] = i;
    }
    
    // Array to use as a stack
    char* stack = (char*)malloc((len + 1) * sizeof(char));
    
    for (int i = 0; i < len; i++) {
        char current = s[i];
        if (seen[current - 'a']) continue;  // Skip if character is already in the result
        
        // Ensure the smallest lexicographical order
        while (stackSize > 0 && stack[stackSize - 1] > current && lastIndex[stack[stackSize - 1] - 'a'] > i) {
            seen[stack[--stackSize] - 'a'] = false;
        }
        
        // Add current character to the stack and mark it as seen
        stack[stackSize++] = current;
        seen[current - 'a'] = true;
    }
    
    // Null-terminate the result string
    stack[stackSize] = '\0';
    
    return stack;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33