https://leetcode.com/problems/longest-substring-without-repeating-characters/
Longest Substring Without Repeating Characters
Total Accepted: 95017 Total Submissions: 467741 Difficulty: Medium
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating characters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.
Idea:
In a string, if you see the same character duplicated at two position `i` and `j`, then the max length of string without duplicated character must either end before `j` or start after `i`.
Use a dictionary in which keys are characters and values correspond to the last positions seeing those characters. Traverse every character of input string `s`. Use a variable `start_pos` to denote what is the foremost starting position of a substring that can end at current position without seeing repeating characters. So the maximum length of non-repeating characters string containing the current character will always be `max(max_len, cur_pos – start_pos + 1)`. If the previous position of seeing current character (`last_pos`) is equal to or after `start_pos`, we need to move `start_pos` one position after `last_pos` because any other string that end at further position can’t start from `last_pos` or before.
Code:
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
start_pos = 0
character_dict = {}
max_len = 0
for i in xrange(len(s)):
last_pos = character_dict.get(s[i], -1)
if last_pos != -1 and last_pos >= start_pos:
start_pos = last_pos + 1
cur_len = i - start_pos + 1
if cur_len > max_len:
max_len = cur_len
character_dict[s[i]] = i
return max_len