Coverage for blog/dsa/leetcode/longest_substring_nonrepeating/__init__.py: 96%

1import pytest 

2 

3 

4# start snippet solution_initial 

5class SolutionInitial: 

6 def longestSubstring(self, s: str) -> tuple[str, int]: 

7 

8 seen: dict[str, int] = dict() 

9 

10 start = 0 

11 best_start, best_stop = 0, 0 

12 best_size = -1 

13 

14 for k, char in enumerate(s): 

15 

16 if (char_last_seen := seen.get(char)) is not None: 

17 start = max(start, char_last_seen + 1) 

18 

19 if (diff := k - start) > best_size: 

20 # print("-->", "new best") 

21 best_start, best_stop = start, k 

22 best_size = diff 

23 

24 seen[char] = k 

25 # print(s) 

26 # print(((start) * " ") + ((diff + 1) * "^")) 

27 

28 if best_size == -1: 

29 return "", 0 

30 

31 return s[best_start : best_stop + 1], 1 + best_stop - best_start 

32 

33 def lengthOfLongestSubstring(self, s: str) -> int: 

34 _, best_size = self.longestSubstring(s) 

35 return best_size 

36 # end snippet solution_initial 

37 

38 

39# start snippet solution 

40class Solution: 

41 def lengthOfLongestSubstring(self, s: str) -> int: 

42 

43 seen: dict[str, int] = dict() 

44 

45 start = 0 

46 best_size = -1 

47 

48 for k, char in enumerate(s): 

49 if char in seen: 

50 start = max(start, seen[char] + 1) 

51 seen.pop(char) 

52 

53 if (diff := k - start) > best_size: 

54 best_size = diff 

55 

56 seen[char] = k 

57 

58 return best_size + 1 

59 # end snippet solution 

60 

61 

62@pytest.fixture 

63def solution_initial(): 

64 return SolutionInitial() 

65 

66 

67@pytest.fixture 

68def solution(): 

69 return Solution() 

70 

71 

72cases = ( 

73 ("nnnnnn", "n"), 

74 ("abcabcbb", "abc"), 

75 ("pwwkew", "wke"), 

76 ("dvdf", "vdf"), 

77 ("peeeeppeepoopooo", "epo"), 

78 ("", ""), 

79) 

80 

81 

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 

88 

89 

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