Longest Substring Without Repeating Characters
Вот в чем я реально тупой, так это в алгоритмах. Последний раз непосредственно алгоритмами занимался в универе, а до этого – в школе на уроках информатики при подготовке к ЕГЭ. Каждый раз, когда меня просят пописать ручкой на листочке или маркером на белой стене алгоритмы в формате live coding, у меня начинается такой скрежет мозгов и тупеж, что это становится слышно через повисшую в воздухе звенящую тишину 😭
Как раз такой и оказалась задачка с LeetCode longest-substring-without-repeating-characters. Сдать ее получилось только с 4-го раза, до этого все решения, основанные на словарях, падали на тест кейсах.
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
nmax = 0
seen = ""
for c in s:
if c in seen:
nmax = max(nmax, len(seen))
idx = seen.find(c)
seen = seen[idx+1:]
seen += c
return max(nmax, len(seen))
В этом решении есть неэффективная работа со строками – скорее всего, этим в том числе объясняется дополнительный расход памяти. Можно попробовать оптимизировать это, заменив строку на массив.
Из-за использования строки, сложность алгоритма в общем случае будет O(n^2). Но в задаче есть такое ограничение.
s consists of English letters, digits, symbols and spaces.А это означает, что даже в худшем случае (когда все символы уникальны) алгоритм будет работать не более чем примерно ~100 символами (это весь английский алфавит в верхнем и нижнем регистре, цифры, символы и пробелы). Возможно, что не 100, а скажем, 1000 (тут все зависит, что мы понимаем под symbols), но смысл в том, что это число ограниченно. И при бесконечном росте N эта константа C будет несущественна.