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

Question

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

Удалите все дубликаты из строки и выберите лексикографическую наименьшую возможную строку. Например, строка cbacdcbc будет возвращать acdb, а не adcb.

Так что это имеет относительно простое решение, если нам не нужно выбирать строку, которая является лексикографической наименьшей, но, учитывая этот факт, я не уверен, как найти эффективное решение. Вот что у меня так далеко:

    string removeDuplicateLetters(string s)
{
vector<bool> v(26,0);
for(int i = 0; i < s.size(); i++) {
v[s[i]-'a'] = 1;
}

string ss = "";
for(int i = 0; i < s.size(); i++) {
if(v[s[i]-'a']) {
ss += s[i];
v[s[i]-'a'] = 0;
}
}

return ss;
}

0

algorithm c++lexicographic string

Решение

По вопросам рекламы [email protected]

Accepted Answer

Алгоритм

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

Пример кода

(в Javascript; мой C ++ ржавый). Это создает немного шаблон 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"));

2

Другие решения

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

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

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

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

0

JavaScript m69 в C ++:

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;
}

0

Источник