Tags: "leetcode", "string", "sliding-window", "hashmap", access_time 1-min read

# 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
``````