0003-longest-substring-without-repeating-characters¶
Try it on leetcode
Description¶
Given a string s, find the length of the longest substring without duplicate characters.
Example 1:
Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Note that"bca"and"cab"are also correct answers.
Example 2:
Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.
Example 3:
Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
Constraints:
0 <= s.length <= 5 * 104sconsists of English letters, digits, symbols and spaces.
Solution(Python)¶
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
return self.optimal(s)
# Time Complexity: O(n^3)
# Space Complexity: O(n)
def bruteforce(self, s: str) -> int:
n = len(s)
long_sub_len = 0
def isUnique(st):
return len(st) == len(set(st))
for i in range(n):
for j in range(i,n):
if isUnique(s[i:j]):
cur_len = j-i
if cur_len > long_sub_len:
long_sub_len = cur_len
return long_sub_len
# Time Complexity: O(n)
# Space Complexity: O(min(m,n))
def better(self, s: str) -> int:
n = len(s)
left = right = 0
hashmap = defaultdict(lambda : 0)
res = 0
while right < n:
hashmap[s[right]] += 1
while hashmap[s[right]] > 1:
hashmap[s[left]] -= 1
left += 1
cur_width = right - left + 1
if cur_width > res:
res = cur_width
right += 1
return res
# Time Complexity: O(n)
# Space Complexity: O(m)
def optimal(self, s: str) -> int:
seen = {}
start = 0
res = 0
for end,c in enumerate(s):
if c in seen:
start = max(start,seen[c]+1)
seen[c] = end
res = max(res ,end-start+1)
return res