Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
[v3] Tested on big texts solution in Clear category for Long Non Repeat by Phil15
# Fast enough on texts with millions of characters.
# from functools import lru_cache
from collections import deque
# @lru_cache(maxsize=None) # Can save a significant time but requires more memory.
def non_repeat(line: str) -> str:
"""The longest substring without repeating chars."""
# Find the first repeating char and list its first two indexes.
indexed_chars = {}
for index, char in enumerate(line):
if char in indexed_chars:
break
indexed_chars[char] = index
else: # No repeating char.
return line
# NOTE: "index < number of different chars", which should be small!
best = line[:index] # No repeating char here.
indexes = deque([indexed_chars[char], index], maxlen=3)
# Find each repetition of the first repeating char to find all
# sub-lines that does not repeat it. Apply our function on it.
while True:
try:
index = line.index(char, index + 1)
except ValueError:
index = None
break
finally:
indexes.append(index)
sub_line = line[indexes[-3] + 1: index]
# `sub_line` is the longest sub-line that does not repeat
# the first repeating char and includes the index `indexes[-2]`.
candidate = non_repeat(sub_line)
if len(candidate) > len(best):
best = candidate
return best
May 19, 2020