[316] Remove Duplicate Letters

其實不太知道自己在幹嘛Orz
這個算是對照著別人的code寫的
神秘的是 strlen(s) 先存起來就從timeout變成4ms !!!
怎麼可能！！！
amazing !!!

給一個字串要把重覆的字拿掉,
但是順序上必須是" smallest in lexicographical order among all possible results."
其實根本不知道是什麼意思Orz
照著例子看就是 需要和它在原本字串出現的順序一樣
但又要最好從 abcde....依序排列
所以如果給 ccbabc
回傳的是 abc 這樣. (感覺古怪的規定 QQ)

雖然不是自己想的
但還是貼上來紀錄一下 QQ
Remove Duplicate Letters
void myRemoveDupLetters(char* s, char *ret, int* size) {
    int len = strlen(s);

    if(len<=0)
        return;
   
    int letters[26] = {0};
    int i;
    for (i=0;i<len;i++)
        letters[s[i]-'a']++;

    int small=0;
    for (i=0;i<len;i++)
    {
        if (s[i] < s[small])
            small = i;
        if (--letters[s[i]-'a'] ==0)
            break;
    }
    char c = s[small];
    *size +=1;
    ret[*size -1] = c;
    int index =0;
    for (i=small+1; i<len; i++)
    {
        if (s[i]!= c)
            s[index++] = s[i];
    }
    s[index] = '\0';
    myRemoveDupLetters(s, ret, size);
}

char* removeDuplicateLetters(char* s) {
    char *ret = malloc(sizeof(char)*27);
    int retSize = 0;
    myRemoveDupLetters(s,ret, &retSize);
    ret[retSize]= '\0';
    return ret;
}

[20220610 update]

沒想到事隔多年我又刷到了同樣這一題而且完全沒有發現這件事XD

然後發現當年沒搞懂果然現在也沒搞懂啊哈哈哈哈哈(奔入雨中)

但有個好消息是現在有 不用recursive的解法了(?)

雖然沒有一個一個印出來之前我還是不知道它在幹嘛, 

但至少比recursive 來的簡單一點Orz

#include <string.h>

char * removeDuplicateLetters(char * s){

    int length = strlen(s);

    int allChar[26]={0,};

    int choose[26]={0,};

    int i,j;

    int retCount=0;

    for (i=0; i<length;i++)

    {

        allChar[s[i]-'a']++;

        if (allChar[s[i]-'a']==1)

            retCount++;

    }

    char *retStr = malloc(sizeof(char)* (retCount+1));

    memset(retStr,0,retCount+1);

    for (i=0,j=0;i<length;i++)

    {

        allChar[s[i]-'a']--;

        if (choose[s[i]-'a'])   //already choose

            continue;

                

        while(j>0 && s[i] < retStr[j-1]  && allChar[retStr[j-1]-'a'] > 0)

        {            

            choose[retStr[j - 1] - 'a']=0;

            j--;

        }

        retStr[j++]=s[i];

        choose[s[i]-'a']=1;

    }    

    retStr[retCount]='\0';

    return retStr;

}