Given a string containing only lowercase letters, please remove the repeated letters in the string so that each letter appears only once. Ensure that the lexicographic order of the returned result is minimal (the relative position of other characters must not be disturbed).

Answer:

  1. Iterate over the string of characters
  2. Checks whether the current character exists in the stack
    1. If it already exists in the stack,
      1. The number of occurrences of this character in record minus one
      2. Continue iterating through the next character in the string
    2. If it doesn’t exist in the stack
      1. Loop (stack not empty + top of stack character > current character + top of stack character occurrence times >1(that is, will appear later)):
        1. The number of occurrences of this character in record minus one
        2. Ejection stack
        3. Until the loop is not satisfied
      2. The current character is pushed
  3. Add ‘\0’ to the top of the stack to form the end of the string character (the actual stack has space for other characters, so the mark \0 indicates the end of the string)

code

char *removeDuplicateLetters(char *s)
{
    if (s == NULL || strlen(s) == 0) return "";
    if (strlen(s) == 1) returns; Record int len = (int)strlen(s); int record[26] = {0}; Char *stack = (char *)malloc(len * sizeof(char)); memset(stack, 0, len * sizeof(char)); Int top = -1; // Count the number of occurrences of each character in the stringfor (int i = 0; i < len; i++) {
        record[s[i]-'a'] + +; } // iterate over each characterfor(int i = 0; i < len; Int isExit = 0; int isExit = 0;for (int j = 0; j <= top; j++) {
            if (stack[j] == s[i]) {
                isExit = 1;
                break; }} // 2, check whether the current character exists in the stack. // ① record in the number of the character appears minus one // ② continue to traverse the next string of characters // ② if the stack does not exist // ① cycle (stack is not empty + stack top character > current character + stack top character of the number of occurrences >1(that will also appear later): // ① the number of times the character appears in the record is reduced by one // ② the stack is pushed out of the stack // ③ until the cycle is not satisfied // ② the current character is pushed onto the stack // 3, the top of the stack is added'\ 0'A string is formed, and the elements on the stack from the bottom of the stack to the top of the stack are the resulting stringif(isExit == 1) {// ① If this character already exists in the stack, // ① the number of this character appears in the record minus a record[s[I]-'a']--;
        }
        else{// ② If the stack does not existwhile (top > -1 && stack[top] > s[i] && record[stack[top]-'a'] >1) {// ① cycle (stack is not empty + stack top character > current character + stack top character of the number of occurrences >1(that will also appear)): // ① record in the number of occurrences of the character minus a record[stack[top]-'a'] -; // * * * * * * * * * * * * * * * * } top++; stack[top] = s[i]; } } stack[++top] ='\ 0';
    
    return stack;
}
Copy the code
int main(int argc, const char * argv[]) {
    
    char *resultString;
    char *originString = "bcabc";
    printf("Enter: %s\n",originString);
    resultString = removeDuplicateLetters(originString);
    printf("%s\n",resultString);
    
    return 0;
}
Copy the code