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 characterbool seen[26] = {false};  // To keep track of seen charactersint stackSize = 0;        // To keep track of stack size// Find the last occurrence of each characterfor (int i = 0; i < len; i++) {lastIndex[s[i] - 'a'] = i;}// Array to use as a stackchar* 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 orderwhile (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 seenstack[stackSize++] = current;seen[current - 'a'] = true;}// Null-terminate the result stringstack[stackSize] = '\0';return stack;
}