Longest Substring Without Repeating Characters
Created: November 21, 2019 by [lek-tin]
Last updated: November 21, 2019
Given a string, find the length of the longest substring without repeating characters.
*### Example 1
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
*### Example 2
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
*### Example 3
Input: "pwwkew"
Output: 3
Explanation: 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.
Solution
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
if s == "":
return 0
lastSeen = {}
start = 0
longest = 0
for i, c in enumerate(s):
if c in lastSeen and lastSeen[c] >= start:
# start counting a new string after the previous occurence of c
start = lastSeen[c] + 1
else:
longest = max(longest, i - start + 1)
# Update the last occurence of c
lastSeen[c] = i
return longest
Python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
uniqueChars = {}
ans, slow, n = 0, 0, len(s)
for fast in range(n):
if s[fast] in uniqueChars:
# take max because of instance like this: "abba"
slow = max(uniqueChars[s[fast]], slow)
ans = max(ans, fast-slow+1)
uniqueChars[s[fast]] = fast+1
return ans