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 будет несущественна.

А что вы думаете про формат live coding на собеседованиях?