67 lines
1.4 KiB
Python
67 lines
1.4 KiB
Python
#!/usr/bin/python
|
|
# yigid balaban <fyb@fybx.dev>
|
|
# neetcode 2024
|
|
# longest substring without repeating characters
|
|
|
|
# my initial solution
|
|
def solution0(s: str) -> int:
|
|
if len(s) <= 1:
|
|
return len(s)
|
|
|
|
longest = -1
|
|
|
|
def count(ss: str):
|
|
c = {}
|
|
for ch in ss:
|
|
if ch in c.keys():
|
|
return 1
|
|
c[ch] = 1
|
|
return len(ss)
|
|
|
|
for f in range(0, len(s)):
|
|
for t in range(f+1, len(s)):
|
|
cs = count(s[f:t+1])
|
|
longest = cs if cs > longest else longest
|
|
|
|
return longest
|
|
|
|
|
|
# hint: sliding window
|
|
def solution(s: str) -> int:
|
|
if len(s) <= 1:
|
|
return len(s)
|
|
|
|
longest = 0
|
|
left = 0
|
|
|
|
def count(ss: str):
|
|
c = {}
|
|
for ch in ss:
|
|
if ch in c.keys():
|
|
return None
|
|
c[ch] = 1
|
|
return len(ss)
|
|
|
|
for right in range(len(s)):
|
|
sample = s[left:right+1]
|
|
cs = count(sample)
|
|
if not cs:
|
|
left = left + 1
|
|
right = left
|
|
else:
|
|
longest = cs
|
|
|
|
return longest
|
|
|
|
|
|
print(solution("") == 0)
|
|
print(solution("a") == 1)
|
|
print(solution("aaa") == 1)
|
|
print(solution("aa") == 1)
|
|
print(solution("ababab") == 2)
|
|
print(solution("xyzyz") == 3)
|
|
print(solution("abcccabcxyz") == 6)
|
|
print(solution("axyzqaxyzqdf") == 7)
|
|
print(solution("wsslpluuwekuaxt") == 7)
|
|
print(solution("wwwwwwwwwsslpluuwekuaxt") == 7)
|