Longest Substring Without Repeating Characters [Medium] — HashSet Window
Sanjeev SharmaAdvertisement
Problem Statement
Find the length of the longest substring without repeating characters.
Input: "abcabcbb" → Output: 3 ("abc")
Input: "bbbbb" → Output: 1 ("b")
Input: "pwwkew" → Output: 3 ("wke")
Intuition
Sliding window with a set tracking current characters. Expand right; if duplicate found, shrink from left until the duplicate is removed.
Optimized: Use lastSeen[char] = index to jump left pointer directly past the previous occurrence.
Solutions
C++
int lengthOfLongestSubstring(string s) {
unordered_map<char,int> last;
int best=0, left=0;
for(int r=0;r<s.size();r++){
if(last.count(s[r])) left=max(left,last[s[r]]+1);
last[s[r]]=r;
best=max(best,r-left+1);
}
return best;
}
Java
public int lengthOfLongestSubstring(String s) {
Map<Character,Integer> last=new HashMap<>();
int best=0, left=0;
for(int r=0;r<s.length();r++){
if(last.containsKey(s.charAt(r))) left=Math.max(left,last.get(s.charAt(r))+1);
last.put(s.charAt(r),r);
best=Math.max(best,r-left+1);
}
return best;
}
JavaScript
var lengthOfLongestSubstring = function(s) {
const last=new Map(); let best=0, left=0;
for(let r=0;r<s.length;r++){
if(last.has(s[r])) left=Math.max(left,last.get(s[r])+1);
last.set(s[r],r);
best=Math.max(best,r-left+1);
}
return best;
};
Python
def lengthOfLongestSubstring(s: str) -> int:
last = {}
best = left = 0
for r, c in enumerate(s):
if c in last and last[c] >= left:
left = last[c] + 1
last[c] = r
best = max(best, r - left + 1)
return best
Complexity
- Time: O(n)
- Space: O(min(m,n)) — character set size
Variants
- Longest Substring with at Most 2 Distinct Characters → k=2 window
- Longest Substring with at Most K Distinct Characters → generalize
Advertisement
