-
Notifications
You must be signed in to change notification settings - Fork 0
/
3_LongestSubstringWithoutRepeatingCharacters.py
118 lines (92 loc) · 3.28 KB
/
3_LongestSubstringWithoutRepeatingCharacters.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
# ----------------------------------
# Question Description
# ----------------------------------
'''
Given a string, find the length of the longest substring without repeating characters.
------------------------------------
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
'''
# ----------------------------------
# My Solution
# ----------------------------------
class Solution:
'''
My solution cause the RecursionError: maximum recursion depth exceeded while calling a Python object.
'''
def __init__(self):
self.maxLength = 0
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
self.findSubString(s)
return self.maxLength
def findSubString(self, targetString):
newLength = 0
subCache = {}
for i, item in enumerate(targetString):
if item not in subCache:
subCache[item] = i
newLength += 1
else:
if newLength > self.maxLength:
self.maxLength = newLength
startPoint = subCache[item] + 1
return self.findSubString(targetString[startPoint:])
# Improved version
class Solution:
def __init__(self):
self.maxLength = 0
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
self.findSubString(s)
return self.maxLength
def findSubString(self, targetString):
newLength = 0
subCache = {}
startPoint = 0
for i, item in enumerate(targetString):
if item not in subCache:
subCache[item] = i
newLength += 1
else:
# change the newLength and replace the index of the repeat item.
cachedIndex = subCache[item]
newLength = i - cachedIndex
subCache[item] = i
# delete the former records
for x in range(startPoint, cachedIndex):
del[subCache[targetString[x]]]
# change the startPoint
startPoint = cachedIndex + 1
# replace the maxLength is needed
if newLength > self.maxLength:
self.maxLength = newLength
# ----------------------------------
# Instruction
# ----------------------------------
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
maxLength, startPoint, cacheList = 0, 0, [False for i in range(256)]
for i, item in enumerate(s):
location = ord(item)
if not cacheList[location]:
cacheList[location] = True
else:
while item != s[startPoint]:
cacheList[ord(s[startPoint])] = False
startPoint += 1
startPoint += 1
maxLength = max(maxLength, i - startPoint + 1)
return maxLength