Coverage for blog/dsa/leetcode/longest_substring_nonrepeating/__init__.py: 96%
51 statements
« prev ^ index » next coverage.py v7.6.12, created at 2025-02-20 16:23 +0000
« prev ^ index » next coverage.py v7.6.12, created at 2025-02-20 16:23 +0000
1import pytest
4# start snippet solution_initial
5class SolutionInitial:
6 def longestSubstring(self, s: str) -> tuple[str, int]:
8 seen: dict[str, int] = dict()
10 start = 0
11 best_start, best_stop = 0, 0
12 best_size = -1
14 for k, char in enumerate(s):
16 if (char_last_seen := seen.get(char)) is not None:
17 start = max(start, char_last_seen + 1)
19 if (diff := k - start) > best_size:
20 # print("-->", "new best")
21 best_start, best_stop = start, k
22 best_size = diff
24 seen[char] = k
25 # print(s)
26 # print(((start) * " ") + ((diff + 1) * "^"))
28 if best_size == -1:
29 return "", 0
31 return s[best_start : best_stop + 1], 1 + best_stop - best_start
33 def lengthOfLongestSubstring(self, s: str) -> int:
34 _, best_size = self.longestSubstring(s)
35 return best_size
36 # end snippet solution_initial
39# start snippet solution
40class Solution:
41 def lengthOfLongestSubstring(self, s: str) -> int:
43 seen: dict[str, int] = dict()
45 start = 0
46 best_size = -1
48 for k, char in enumerate(s):
49 if char in seen:
50 start = max(start, seen[char] + 1)
51 seen.pop(char)
53 if (diff := k - start) > best_size:
54 best_size = diff
56 seen[char] = k
58 return best_size + 1
59 # end snippet solution
62@pytest.fixture
63def solution_initial():
64 return SolutionInitial()
67@pytest.fixture
68def solution():
69 return Solution()
72cases = (
73 ("nnnnnn", "n"),
74 ("abcabcbb", "abc"),
75 ("pwwkew", "wke"),
76 ("dvdf", "vdf"),
77 ("peeeeppeepoopooo", "epo"),
78 ("", ""),
79)
82@pytest.mark.parametrize("question, answer", cases)
83def test_solution_init(solution_initial: SolutionInitial, question: str, answer: str):
84 got, got_size = solution_initial.longestSubstring(question)
85 print(got, answer)
86 assert got == answer
87 assert len(got) == got_size
90@pytest.mark.parametrize("question, answer", cases)
91def test_solution(solution: Solution, question: str, answer: str):
92 got_size = solution.lengthOfLongestSubstring(question)
93 print(got_size, len(answer))
94 assert len(answer) == got_size