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


    示例 1: 输入: "bcabc" 输出: "abc" 示例 2: 输入: "cbacdcbc" 输出: "acdb"

    解题之前我们需要先搞清楚什么是字典序，所谓字典序就是两个字符串按照每个字母的 ASCII 顺序进行排序。比如串1为 abc ，串2为 acd ，第一个字符都为 a ,而第二个字符分别是 b 和 c ，而在 ASCII 表中， b 小于 c ，所以串1的字典序小于串2。
    其次我们需要注意题目的要求是不能打乱字符的相对位置。

    下面开始展开我们的思路:

    • 如果给定的字符串 S 为空，或者 S 长度为1，那么直接返回即可
    • 数组 record 记录字母出现的次数，因为有 26 个英文字母，所以 record 长度为 26 同时完成字母出现次数循环计算
    • 字符栈 stack 先进后出思想：存储去除重复自己的结果，利用栈来正确次序
    • 遍历字符串 S，当前字符 i
      • 0 ~ top 范围内，判断当前字符是否已经在栈中
      • 如果已经存在，record[s[i]]—，继续遍历下一个字符，表示 stack 已经有这个字符，没有必要重复存储这个字符
      • 不存在，通过 while 循环找到正确的位置
        • stack 不能为空 top > -1
        • stack[top] > s[i]
        • 栈顶字符对应出现次数不能为1
      • top++ 入栈

    最后我们上代码:

    1. char *removeDubplicateLetters(char *s)
    2. {
    3.     if (s == NULL || strlen(s) == 0) return "";
    4.     if (strlen(s) == 1) return s;
    6.     // record 记录字母出现次数
    7.     // stack 存储结果以及利用栈思想来寻找位置
    8.     char record[26] = {0};
    9.     int len = (int)strlen(s);
    10.     char *stack = (char *)malloc(len * 2 * sizeof(char));
    11.     memset(stack, 0, len * 2 * sizeof(char));
    12.     int top = -1;
    14.     // 统计字母出现次数
    15.     int i = 0;
    16.     for (i = 0; i < len;i++) {
    17.         record[s[i] - 'a']++;
    18.     }
    20.     // 遍历字符串S
    21.     for (i = 0;i < len;i++) {
    22.         // 标记，当前字母是否在 stack 存在
    23.         int isExist = 0;
    25.         // 字符是否已经在栈中存储
    26.         for (int j = 0; j <= top; j++) {
    27.             if (s[i] == stack[j]) {
    28.                 isExist = 1;
    29.                 break;
    30.             }
    31.         }
    33.         if (isExist == 1) {
    34.             record[s[i] - 'a']--;
    35.         } else {
    36.             while (top > -1 && stack[top] > s[i] && record[stack[top] - 'a'] > 1) {
    37.                 // 跳过该元素，频次减一
    38.                 record[stack[top] - 'a']--;
    39.                 // 出栈
    40.                 top--;
    41.             }
    42.             stack[++top] = s[i];
    43.         }
    44.     }
    45.     stack[++top] = '\0';
    46.     return stack;
    47. }

    leetcode 提交截图:
    image.png