Выберите лексикографическую наименьшую строку после удаления дубликатов

Алгоритм

1. Проверить, какие буквы присутствуют во входной строке: a,b,c,d.
2. Найдите первый a, за которым следуют все b,c,d.
   Или, если это невозможно, найдите первый b, за которым следуют все a,c,d.
   Или, если это невозможно, найдите первый c, за которым следуют все a,b,d после нее.
   Или, если это невозможно, найдите первую d.
3. Отменить начало входной строки до выбранного символа.
4. Повторите с шага 2 с оставшимися символами, которые нужно найти.

Пример кода

(в Javascript; мой С++ ржавый). Он создает битовый шаблон chars для хранения символов, которые еще предстоит найти, и массив битовых шаблонов after для хранения доступных символов после каждой позиции.

function smallestString(input) {
    var chars = 0, after = [];
    for (var i = input.length - 1; i >= 0; i--) {
        chars |= 1 << (input.charCodeAt(i) - 97);
        after[i] = chars;
    }
    var result = "", start = 0, pos;
    while (chars) {
        for (var i = 0; i < 26; i++) {
            if (chars & (1 << i)) {
                pos = input.indexOf(String.fromCharCode(97 + i), start);
                if (chars == (chars & after[pos])) {
                    result += String.fromCharCode(97 + i);
                    chars -= 1 << i;
                    break;
                }
            }
        }
        start = pos + 1;
    }
    return result;
}

document.write(smallestString("cbacdcbc") + "<BR>");
document.write(smallestString("thequickbrownfoxjumpsoverthelazydog"));

JavaScript m69 в С++:

string smallestString(string input) {
    int chars = 0;
    int after[sizeof(input)];
    for (int i = input.length() - 1; i >= 0; i--) {
        chars |= 1 << (input[i] - 97);
        after[i] = chars;
    }
    string result = "";
    int start = 0, pos;
    while (chars) {
        for (int i = 0; i < 26; i++) {
            if (chars & (1 << i)) {
                pos = input.find('a' + i, start);
                if (chars == (chars & after[pos])) {
                    result += 'a' + i;
                    chars -= 1 << i;
                    break;
                }
            }
        }
        start = pos + 1;
    }
    return result;
}

Набросок алгоритма.

1. Пропустите строку, постройте карту того, сколько раз появляется каждый символ, и положение самого правого (и, возможно, единственного) вхождения каждого символа.

2. Найдите наименьший символ, который может появиться на первой позиции. Для этого идите слева направо, отмечая самый маленький встретившийся символ; остановитесь, когда вы нажмете самое правое вхождение любого символа. Удалите все символы, предшествующие наименьшему, и все остальные копии наименьшего; обновить карту соответственно.

3. Повторите, начиная с символа, который сразу следует за самым маленьким из шага № 2.

Может завершиться досрочно, как только все счетчики в карте достигнут 1. Удаление других копий можно совместить с обычной итерацией (просто пометьте удаляемые символы 0 в карте счетчиков, пропустите их при обычном поиске, удалите их, когда удаление префикса).

Этот алгоритм является квадратичным в худшем случае, по крайней мере, в отношении размера алфавита (худший случай — abc...zabc...; алгоритм проверяет половину строки для каждого символа только для того, чтобы решить оставить ее). Я думаю, что это можно исправить, отслеживая не только наименьшие, но и вторые и третьи наименьшие и так далее, в своего рода структуре приоритетной очереди (подробности оставлены в качестве упражнения для читателя).

Я нахожу этот подход простым.

Сначала найдите количество каждого символа.

ввод: с

vector<int> cnt(26);
int n=s.size();
for(int i=0;i<n;i++) cnt[s[i]-'a']++;

Посетил вектор, vector<bool> visit(26);

string ans="";
for(int i=0;i<n;i++){
    int t=s[i]-'a';
    cnt[t]--;
    if(visit[t]) continue;
    while(ans.size()>0 && s[i]<ans.back() && cnt[ans.back()-'a']>0){
        visit[ans.back()-'a']=false;
        ans.pop_back();
    }
    ans.push_back(s[i]);
    visit[t]=true;
}
return ans;

Временная сложность O (n)