Написано: 23.02.2023
3. Longest Substring Without Repeating Characters
Задание.
Получена строка s.
Нужно найти длину самой длинной подстроки без повторяющихся символов.
Пример 1.
Входные данные: s = “abcabcbb”
Результат: 3
Пояснение: Подстрока – “abc”, длина которой равна 3.
Пример 2.
Входные данные: s = “bbbbb”
Результат: 1
Пояснение: Подстрока – “b”, длина которой равна 1.
Пример 3.
Входные данные: s = “pwwkew”
Результат: 3
Пояснение: Ответ – “wke”, длина которого равна 3. Обратите внимание, что ответ должен быть подстрокой, “pwke” – это подпоследовательность, а не подстрока.
Решение.
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int windowStart = 0;
int maxLength = 0;
unordered_map<char, int> charmap;
char rightchar;
for (int windowEnd = 0; windowEnd < (int)s.size(); windowEnd++) {
rightchar = s[windowEnd];
if (charmap.find(rightchar) != charmap.end()) {
windowStart = max(windowStart, charmap[rightchar] + 1);
}
charmap[rightchar] = windowEnd;
maxLength = max(maxLength, windowEnd - windowStart + 1);
}
return maxLength;
}
};
Пояснение (на примере).
