3. Longest Substring Without Repeating Characters
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.
Solution: HashMap
Python
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
max_len = 0
pre_pos = dict()
slow = 0
for fast, char in enumerate(s):
if char in pre_pos:
slow = max(slow, pre_pos[char] + 1)
pre_pos[char] = fast
max_len = max(max_len, fast - slow + 1)
return max_len
JavaScript
/**
* @param {string} s
* @return {number}
*/
const lengthOfLongestSubstring = (s) => {
let maxLength = 0;
const index = {};
let i = 0;
let j = 0;
while (j < s.length) {
const letter = s.charAt(j);
if (index.hasOwnProperty(letter)) {
i = Math.max(i, index[letter] + 1);
}
maxLength = Math.max(maxLength, j - i + 1);
index[letter] = j;
j += 1;
}
return maxLength;
};