去除重复字符问题的解析

1.题目

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

实例1

输入：bcabc

输出：abc

从题目中我们可以得到如下信息

1、 去除重复字符
2、 结果字典序最小
3、 不能打乱字符的相对位置

2. 解析

1、 创建字符串stack，利用栈思想先进先出，存储去重&字典序最小&不打乱位置后的结果
2、 遍历字符串，其中遍历字符串stack，判断当前字符是否已经存在stack栈中，用一个标记isExist记录
3、 标记存在，需要在record数组中将对应字母位置的次数进行自减
4、 标记不存在，通过一个while循环来找到当前字符的正确位置，满足如下的话进行出栈操作

栈不能为空栈 top>-1
栈顶元素大于了当前元素 (这里是为了字典序最小)
record数组汇总，当前元素的个数大于1 (这里是为了不打乱位置)

5、之后top自加，当前元素入栈

3. 实现

char *removeDuplicateLetters(char *s){
    // 首先要判断字符是否为空
    if (s == NULL || strlen(s) == 0) {
        return "";
    }
    if (strlen(s) == 1) {
        return s;
    }

    // 记录字符出现的次数
    char record[26] = {0};
    int len = (int)strlen(s);

    // 记录去重后的 最小字典序结果 空间*2 可以灵活调整，但最少要比len大1，因为最终要加'\0'结束符
    char *stack = (char *)malloc(sizeof(char)*len*2);
    // 给stack栈赋初值 0
    memset(stack, 0, len*2*sizeof(char));

    int i;
    int top = -1;
    // 遍历字符串 在record数组中 记录字符串中的字符 出现的个数
    for (i = 0; i<len; i++) {
        record[s[i]-'a']++; // 利用ASCII码 保存字符的出现个数
    }

    // 遍历整个字符
    for (int i = 0; i<len; i++) {

        /*
           isExist 判断当前的s[i]的值 是否在栈中，
           是的话 record需要减去它的在字符串中出现的个数
         */
        /* 此时栈中的数据已经经历了while循环的过程，栈中的数据已经是字典序
           最小的排列，如果之后还有 相等于栈中的数据时，可以直接自减它在record
           中出现的个数 而不必再做其他操作
         */
        int isExist = 0;
        for (int j = 0; j<top; j++) {
            if (s[i] == stack[j]) {
                isExist = 1;
                break;
            }
        }

        if (isExist) {
            record[s[i]-'a']--;
        }else{
            /*
             while循环 判断栈顶元素大于当前元素
             且 栈顶元素在record中出现次数大于1
             即 在字符串后续还会出现 那么就出栈 top自减
             */
            while (top>-1 && stack[top]>s[i]&&record[stack[top]-'a']>1) {
                record[s[i]-'a']--;
                top--;
            }
            /*
            while循环结束后 栈中的元素进行了调整 当前元素在进行入栈
            保证字典序最小 & 位置不被打乱
            */ 
            top++;
            stack[top] = s[i];
        }
    }
    stack[++top] = '\0';
    return stack;
}

3. 结果

char *s ;
s = removeDuplicateLetters("bcabc");
printf("%s\n",s);
// 输出结果 abc

文章永久链接：https://tech.souyunku.com/31414