去除重复字母（LeetCode-316）

LeetCode-316
给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

示例

输入: "bcabc"
输出: "abc"

输入: "cbacdcbc"
输出: "acdb"

解题思路

1. 初始化一个数组record[26];
2. 遍历s记录每个字母出现的次数;
3. 申请一个字符串栈stack用来存储去除重复字母的结果，遍历s进行入栈；
4. 遍历栈，如果s[i]存在于栈中，则record[s[i] - 'a']--,并且继续下一次遍历；
5. 否则比较栈顶字母和s[i]的大小，如果stack[top]>s[i]并且record[stack[top]-'a']>1(说明stack[top]在后边还会出现)就出栈，并且record[s[i]-’a‘]--；
6. 入栈；
7. 最后stack[++top]=’\0‘转成字符串;

代码实现

char * removeDuplicateLetters(char * s) {
    int len = (int)strlen(s);
    if (s == NULL && len == 0) {
        return "";
    }
    
    if (len == 1) {
        return s;
    }
    
    char record[26] = {0};
    char *stack = (char *)malloc(sizeof(char) * len << 2);
    int top = -1;
    memset(stack, 0, sizeof(char) * len << 2);
    
    for (int i = 0; i < len; i++) {
        record[s[i] - 'a']++;
    }
    
    for (int i = 0; i < len; i++) {
        int isExist = 0;
        for (int j = 0; j <= top; j++) {
            if (stack[j] == s[i]) {
                isExist = 1;
                break;
            }
        }
        
        if (isExist == 1) {
            record[s[i] - 'a']--;
        } else {
            while (top > -1 && stack[top] > s[i] && record[stack[top] - 'a'] > 1) {
                record[stack[top] - 'a']--;
                top--;
            }
            stack[++top] = s[i];
        }
    }
    
    stack[++top] = '\0';
    return stack;
}

Demo：https://github.com/ShoukaiWang/DataStructuresAndAlgorithms