Я полагаю, что в алгоритме OP что-то не так (или, по крайней мере, отсутствует).
Я не полностью понял алгоритм, но, по крайней мере, до такой степени, что вхождение символов считается.Если count для определенного символа не равно 1, то обнаруживается дубликат, и массив count полностью сбрасывается.ИМХО это неправильный момент.Массив count вырождается в массив флагов (и этого недостаточно).
Пример счетчика pwwkwe:
- дублируется при
s[2] - сброс
count (то есть перезапуск) - дублирование при
s[4] - сброс
count (то есть перезапуск).
Следовательно, самая длинная обнаруженная подстрока будетимеют длину не более 2. Но начиная с k это на самом деле 3 (kwe).
Итак, у меня возникла другая идея:
Как только обнаружен дубликатсамая длинная подстрока может фактически начинаться сразу за предыдущим вхождением этого символа.Учитывая это, дубликат больше не является дубликатом.
Это может показаться немного запутанным.Может быть, становится легче понять, когда я покажу, как я решил это:
count больше не используется в качестве массива флагов.Вместо этого там хранится индекс последнего вхождения (для каждого символа).Таким образом, для каждого символа можно проверить расстояние до его предыдущего появления (которое не содержит дубликатов этого символа).Но он не должен содержать дубликатов.Поэтому я дополнительно ввел начальный индекс (i0), который всегда устанавливается один раз за предыдущее вхождение символа.(Дубликаты до начального индекса не рассматриваются.) Таким образом, при определении правильной подстроки учитывается только последний дубликат.
В коде:
#include <iostream>
#include <string>
/* determines longest substring without duplicated characters.
* param s ... string to evaluate
* return: pair of
* first ... start index of found substring
* second ... length of found substring
*/
std::pair<int, int> lengthOfLongestSubstring(const std::string &s)
{
// index of last occurrence for each character
// (-1 ... character not yet occurred)
int iChrLast[256];
for (int &i : iChrLast) i = -1;
// result start index, length
std::pair<int, int> result(0, 0);
// check all characters (i0 ... current start)
for (int i = 0, i0 = 0; i < (int)s.length(); ++i) {
// cast char to index (via (unsigned char) to prevent negative indices)
const int c = (unsigned char)s[i];
// check if there is a duplicate after current start
if (iChrLast[c] >= i0) i0 = iChrLast[c] + 1;
// compute length with current start
const int len = i - i0 + 1;
// check whether new max. length found (update in case)
if (result.second < len) result = std::make_pair(i0, len);
// remember last occurrence of this char
iChrLast[c] = i;
}
// done
return result;
}
int main()
{
const std::string tests[] = {
"abcabcbb",
"bbbbb",
"pwwkew"
};
for (const std::string &test : tests) {
const std::pair<int, int> result = lengthOfLongestSubstring(test);
std::cout << test << ": " << result.first << ", " << result.second
<< " ("<< test.substr(result.first, result.second) << ")\n";
}
return 0;
}
Вывод:
abcabcbb: 0, 3 (abc)
bbbbb: 0, 1 (b)
pwwkew: 2, 3 (wke)
Демонстрация в реальном времени на coliru
Я должен признать, что согласен с Крейгом Янгом, что
Программирование не связано с изучением того, какие ошибки «не повторять».Речь идет о понимании происходящих изменений состояния, причинно-следственной связи и выяснении того, когда и почему это не работает так, как вы ожидаете.
Я пытался решить это (как загадку), предполагая,что некоторый вид отслеживания или даже рекурсия были бы необходимы.Итак, я немного удивился, когда наконец нашел это решение.(И как только я запустил его, я не удержался, чтобы опубликовать это как ответ.)
Как вы научились создавать алгоритмы?Может быть, талант, может быть, опыт, и, конечно, много практики ...