給你一個(gè)僅包含小寫(xiě)字母的字符串，請(qǐng)你去除字符串中重復(fù)的字母，使得每個(gè)字母只出現(xiàn)一次。需保證返回結(jié)果的字典序最小（要求不能打亂其他字符的相對(duì)位置）

示例1:
input:"bcabc"
output:"abc"

示例2:
輸入:"cbacdcbc"
輸出:"acdb"

概念

一、字典序

字典序，就是按照字典中出現(xiàn)的先后順序進(jìn)行排序。

1、單個(gè)字符

在計(jì)算機(jī)中，字母以及數(shù)字字符，字典排序如下：
'0' < '1' < '2' < ... < '9' < 'a' < 'b' < ... < 'z'

2、多個(gè)字符

這是單個(gè)字符的大小情況，那么如果是兩個(gè)字符串比較大小呢？在計(jì)算機(jī)中，兩個(gè)字符串比較大小，是按照從左到右的順序進(jìn)行比較，如果第1位相等，就比較第2位，直至有一位可以比較出大小來(lái)，則不再繼續(xù)比較。

使用計(jì)算機(jī)屬于來(lái)描述：

對(duì)于任意兩個(gè)序列 (a,b) 和 (a’,b’)，字典序定義為： (a,b) ≤ (a′,b′) 當(dāng)且僅當(dāng) a < a′ 或 (a = a′ 且 b ≤ b′).

3、全排列的字典序

給定多個(gè)字符，可以按照任意順序進(jìn)行排列，所有排列稱為全排列。每一種排列對(duì)應(yīng)一個(gè)字符串，如果這些字符串按照字符串大小的順序進(jìn)行排序，那么就這種排序是基于字典序的全排列。

比如給定三個(gè)字符 a,b,c，則他們基于字典序的全排列為：
abc > acb > bac > bca > cab > cba

解題

注意點(diǎn)

字典序要最小，并且不能更改相對(duì)位置，字母互換

思路

1. 字符串S為空，長(zhǎng)度為1，不需要處理
2. 使用一個(gè)數(shù)組記錄每個(gè)字母出現(xiàn)次數(shù) record [26]
3. 字符串棧stack，用來(lái)去除重復(fù)字母的結(jié)果，并且找到正確最小的字典序
4. 遍歷字符串
5. 從0~top,遍歷stack 判斷當(dāng)前字符s[i]是否存在于棧stack中如果當(dāng)前字符是否存在于棧的定義一個(gè)falg 標(biāo)記isExist, 0表示不存在, 1表示存在
6. 如果isExist存在,record[s[i]]位置上的出現(xiàn)次數(shù)減一，并繼續(xù)遍歷下一個(gè)字符; 表示當(dāng)前的stack已經(jīng)有這個(gè)字符了沒(méi)有必要處理這個(gè)重復(fù)的字母
7. 如果isExist不存在,則
   • 如果不存在,則需要循環(huán)一個(gè)找到一個(gè)正確的位置,然后在存儲(chǔ)起來(lái);
   • 如果不存在，跳過(guò)棧中所有比當(dāng)前字符大、且后面還會(huì)出現(xiàn)的元素，然后將當(dāng)前字符入棧
   • top > -1表示棧非空
   • stack[top] > s[i]表示棧頂元素比當(dāng)前元素大
   • record[stack[top]] > 1表示后面還會(huì)出現(xiàn)
     通過(guò)一個(gè)while循環(huán)找到將棧中位置錯(cuò)誤的數(shù)據(jù),出棧. 找當(dāng)前合適的位置,則結(jié)束while循環(huán);找到合理的位置后,則將當(dāng)前字符s[i]入棧
8. 遍歷完成后，在stack 后添加'\0',返回當(dāng)前字符串首地址

代碼

char *removeCharacter(char *string) {
    // 1、特殊情況 s為空，長(zhǎng)度為0
    //2、s長(zhǎng)度為1
    if (string == NULL || strlen(string) == 0 ) {
        return "";
    }
    if (strlen(string) == 1) {
        return string;
    }
    char record[26] = {0};
    // 字符串長(zhǎng)度
    int len = (int)strlen(string);
    // 存儲(chǔ)不用字符
    char *stack = (char *)malloc(len * 2 *sizeof(char));
    memset(stack, 0, len * 2 *sizeof(char));
    int top = -1;
    
    // 統(tǒng)計(jì)每個(gè)字母出現(xiàn)次數(shù)
    // string[i] - 'a' 利用asc碼得道每個(gè)字母的位置，記錄到record中
    int i = 0;
    for (i = 0; i < len; i++) {
        record[string[i] - 'a']++;
    }
    
    // 遍歷字符串s，把不相同的字母進(jìn)棧
    for (i = 0; i < len; i++) {
        int isExist = 0;
        // 判斷當(dāng)前字符在棧里面是否存在
        for (int j = 0; j <= top; j++) {
            if (string[i] == stack[j]) {
                isExist = 1;
                break;
            }
        }
        
        if (isExist == 1) {
            record[string[i] - 'a']--;
        } else {
            while (top > -1 && stack[top] > string[i] && record[stack[top] - 'a'] > 1) {
                record[stack[top] - 'a']--;
                top--;
            }
            top++;
            stack[top] = string[i];
        }
    }
    stack[++top] = '\0';
    return stack;
}