【算法题】13.去除重复字母

题目

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

示例1:

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

示例2:

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

解析：

1. 用哈希表记录每个字符出现的次数，用于判断是否具有相同元素。
2. 用栈来存储最终返回的字符串，并维持字符串的最小字典序。
3. 每遇到一个字符，如果这个字符不存在于栈中，就需要将该字符压入栈中。
4. 但在压入之前，需要先将之后还会出现，并且字典序比当前字符小的栈顶字符移除，然后再将当前字符压入。

顺序队列-假溢出

复杂度分析：

时间复杂度：
空间复杂度：

代码

char * removeDuplicateLetters(char * s){
  char * result = (char *)malloc(sizeof(char) * 27);

  int * unUsedAscii = (int *)calloc(26,sizeof(int));

  int * usedAscii = (int *)calloc(26,sizeof(int));

   
  int length = strlen(s);

  for (int i = 0; i < length; I++)
  {
     char c = s[I];
     int index = c - 'a';
     unUsedAscii[index]++;
  }
  
  int top = -1;

  int i = 0;

  while (i < length){
     char c = s[I];
     int index = c - 'a';
     
     if (top == -1)
     {
        top++;
        result[top] = s[I];
        usedAscii[index]++;
        unUsedAscii[index]--;
        I++;
     }else if(result[top] > s[I]){

        if (usedAscii[index] > 0)
        {
           unUsedAscii[index]--;
           I++;
        }else{
        
            int index1 =  unUsedAscii[result[top] - 'a'];
            if (index1 > 0){
                usedAscii[result[top]-'a']--;
                result[top] = '\0';
                top--;
            }else{
               top++;
               result[top] = s[I];
               usedAscii[index]++;
               unUsedAscii[index]--;
               I++;
               
            }
        }
        
     }else if (result[top] < s[I]){

         printf("%c----%d\n",s[i],usedAscii[index] );        
         if (usedAscii[index] < 1)
         {

            top++;
            usedAscii[index]++;
            result[top] = s[I];
           
         }
         unUsedAscii[index]--;
         I++;
          
     }else{
        unUsedAscii[index]--;
        I++;
        
     }
      
        
  }
  top++;
  result[top] = '\0';
  return result;

}