C++去除字符串中重复字母

思路：

1. 定义一个布尔类型的数组 used，用于记录每个字符是否已经出现过。

2. 定义一个栈 stack，用于存储最终的结果。

3. 遍历字符串，对于每个字符：

- 如果该字符已经出现过（used[c] 为真），则直接跳过；

- 如果该字符比栈顶元素小（即该字符在栈顶元素之前出现过），则弹出栈顶元素，直到栈顶元素不大于该字符为止；

- 将该字符压入栈中，并将 used[c] 设置为真。

4. 将栈中的元素依次弹出并拼接成字符串，即为结果。

代码实现：

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

char* removeDuplicateLetters(char* s) {
    int len = strlen(s);
    bool used[26] = {false}; // 记录每个字符是否已经出现过
    int count[26] = {0}; // 记录每个字符出现的次数
    for (int i = 0; i < len; i++) {
        count[s[i] - 'a']++;
    }
    char stack[len + 1]; // 定义栈
    int top = -1; // 栈顶指针
    for (int i = 0; i < len; i++) {
        int c = s[i] - 'a';
        if (used[c]) {
            count[c]--;
            continue;
        }
        while (top >= 0 && stack[top] > s[i] && count[stack[top] - 'a'] > 0) {
            used[stack[top] - 'a'] = false;
            top--;
        }
        stack[++top] = s[i];
        used[c] = true;
        count[c]--;
    }
    stack[top + 1] = '\0'; // 栈顶指针加 1，用 '\0' 结束字符串
    return stack;
}

int main() {
    char s[] = "bcabc";
    char* result = removeDuplicateLetters(s);
    printf("%s\n", result); // 输出 "abc"
    return 0;
}

时间复杂度：O(n)，其中 n 是字符串的长度。遍历字符串一遍的时间复杂度是 O(n)，弹出栈顶元素的时间复杂度也是 O(n)，因此总时间复杂度是 O(n)。

空间复杂度：O(1)。由于只涉及到字符集大小的常数级别的空间开销，因此空间复杂度是 O(1)。