给定字符串 s， 其特征子序列 t 满足： 子序列中的字符各不相同； s 中的各种字符都能在 t 中找到； 对于一个字符串 s，可能会对应多个特征子序列，其中字典序最小的特征序列称为“最优特征子序列”。 请写一个程序，返回字符串的最优特征子序列。要求时间复杂度不超过 O(N)。要求输入一行长度为N。然后输入一行长度为N的s字符串。输出要求的最优特征子序列。用C++代码实现

以下是C++代码实现：

#include <iostream>
#include <cstring>

using namespace std;

const int MAXN = 26;

char s[MAXN + 5]; // 输入的字符串
int cnt[MAXN + 5]; // 统计每个字符出现的次数
bool vis[MAXN + 5]; // 记录每个字符是否在特征子序列中出现过

int main() {
    cin >> s;
    int n = strlen(s);

    for (int i = 0; i < n; i++) {
        cnt[s[i] - 'a']++; // 统计每个字符出现的次数
    }

    for (int i = 0; i < n; i++) {
        if (!vis[s[i] - 'a']) { // 如果当前字符还没有出现在特征子序列中
            while (!vis[s[i] - 'a'] && // 如果当前字符还没有出现在特征子序列中
                   cnt[s[i] - 'a'] > 0 && // 当前字符在剩余未处理的字符中仍然存在
                   (s[i] < s[n - 1] || cnt[s[i] - 'a'] > 1)) { // 当前字符比剩余未处理的字符中的最后一个字符小，或者当前字符在剩余未处理的字符中出现了多次
                vis[s[i] - 'a'] = true; // 标记当前字符出现在特征子序列中
                cnt[s[i] - 'a']--; // 将当前字符从剩余未处理的字符中删除
                cout << s[i];
            }
        }
    }

    cout << endl;

    return 0;
}

算法思路：

1. 统计每个字符出现的次数。

2. 对于输入的字符串 s，按照顺序依次处理每个字符。

3. 对于每个字符，如果它还没有出现在特征子序列中，就尝试将它加入到特征子序列中。

4. 如果当前字符在剩余未处理的字符中仍然存在，并且当前字符比剩余未处理的字符中的最后一个字符小，或者当前字符在剩余未处理的字符中出现了多次，那么就将当前字符加入到特征子序列中。

5. 不断重复步骤 4，直到不能再加入新的字符为止。

6. 输出特征子序列即为最优特征子序列。

时间复杂度为 O(N)。