Problem Statement:
Given a string s, find the length of the longest substring without duplicate characters.
Examples:
Example 1:
Input: s = “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2:
Input: s = “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
Example 3:
Input: s = “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.
Constraints:
0 <= s.length <= 5 * 104sconsists of English letters, digits, symbols and spaces.
Approach
- A hash map map stores the most recent index of each character.
- If we encounter a repeating character that’s
within the current window, we move the start pointer i just after its last occurrence. - At each step, we calculate the window size and update the maximum length
maxWS.
Using two pointers i and j to form a sliding window that keeps track of the current substring without repeating characters.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(n)
Dry Run
Input: s = "abcabcbb"
Initialize: i = 0, j = 0, map = {}, maxWS = 0
// Iteration over j
j = 0 → s[j] = 'a'
→ 'a' not in map
→ map = { a: 0 }
→ currWS = 0 - 0 + 1 = 1
→ maxWS = max(0, 1) = 1
j = 1 → s[j] = 'b'
→ 'b' not in map
→ map = { a: 0, b: 1 }
→ currWS = 1 - 0 + 1 = 2
→ maxWS = max(1, 2) = 2
j = 2 → s[j] = 'c'
→ 'c' not in map
→ map = { a: 0, b: 1, c: 2 }
→ currWS = 2 - 0 + 1 = 3
→ maxWS = max(2, 3) = 3
j = 3 → s[j] = 'a'
→ 'a' in map and map['a'] = 0 ≥ i
→ i = map['a'] + 1 = 1
→ map = { a: 3, b: 1, c: 2 }
→ currWS = 3 - 1 + 1 = 3
→ maxWS = max(3, 3) = 3
j = 4 → s[j] = 'b'
→ 'b' in map and map['b'] = 1 ≥ i
→ i = map['b'] + 1 = 2
→ map = { a: 3, b: 4, c: 2 }
→ currWS = 4 - 2 + 1 = 3
→ maxWS = max(3, 3) = 3
j = 5 → s[j] = 'c'
→ 'c' in map and map['c'] = 2 ≥ i
→ i = map['c'] + 1 = 3
→ map = { a: 3, b: 4, c: 5 }
→ currWS = 5 - 3 + 1 = 3
→ maxWS = max(3, 3) = 3
j = 6 → s[j] = 'b'
→ 'b' in map and map['b'] = 4 ≥ i
→ i = map['b'] + 1 = 5
→ map = { a: 3, b: 6, c: 5 }
→ currWS = 6 - 5 + 1 = 2
→ maxWS = max(3, 2) = 3
j = 7 → s[j] = 'b'
→ 'b' in map and map['b'] = 6 ≥ i
→ i = map['b'] + 1 = 7
→ map = { a: 3, b: 7, c: 5 }
→ currWS = 7 - 7 + 1 = 1
→ maxWS = max(3, 1) = 3
Final map = { a: 3, b: 7, c: 5 }
Final maxWS = 3
Output: Result: 3
Visualisation:
var lengthOfLongestSubstring = function(s) {
let i = j = 0;
let map = {};
let maxWS = 0;
for(j=0; j= i){
i = map[s[j]] + 1;
}
map[s[j]] = j;
currWS = j - i + 1;
maxWS = Math.max(maxWS, currWS);
}
return maxWS;
};
def lengthOfLongestSubstring(s: str) -> int:
map = {}
maxWS = 0
i = 0
for j in range(len(s)):
if s[j] in map and map[s[j]] >= i:
i = map[s[j]] + 1
map[s[j]] = j
currWS = j - i + 1
maxWS = max(maxWS, currWS)
return maxWS
import java.util.HashMap;
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap map = new HashMap<>();
int maxWS = 0;
int i = 0;
for (int j = 0; j < s.length(); j++) {
if (map.containsKey(s.charAt(j)) && map.get(s.charAt(j)) >= i) {
i = map.get(s.charAt(j)) + 1;
}
map.put(s.charAt(j), j);
int currWS = j - i + 1;
maxWS = Math.max(maxWS, currWS);
}
return maxWS;
}
}
#include <iostream>
#include <unordered_map>
using namespace std;
int lengthOfLongestSubstring(string s) {
unordered_map map;
int maxWS = 0, i = 0;
for (int j = 0; j < s.length(); j++) {
if (map.find(s[j]) != map.end() && map[s[j]] >= i) {
i = map[s[j]] + 1;
}
map[s[j]] = j;
int currWS = j - i + 1;
maxWS = max(maxWS, currWS);
}
return maxWS;
}
#include <stdio.h>
#include <string.h>
int lengthOfLongestSubstring(char* s) {
int lastIndex[256];
for (int i = 0; i < 256; i++) {
lastIndex[i] = -1;
}
int maxWS = 0, i = 0;
for (int j = 0; s[j] != '\0'; j++) {
if (lastIndex[(unsigned char)s[j]] >= i) {
i = lastIndex[(unsigned char)s[j]] + 1;
}
lastIndex[(unsigned char)s[j]] = j;
int currWS = j - i + 1;
if (currWS > maxWS) {
maxWS = currWS;
}
}
return maxWS;
}
using System;
using System.Collections.Generic;
public class Solution {
public int LengthOfLongestSubstring(string s) {
Dictionary map = new Dictionary();
int maxWS = 0, i = 0;
for (int j = 0; j < s.Length; j++) {
if (map.ContainsKey(s[j]) && map[s[j]] >= i) {
i = map[s[j]] + 1;
}
map[s[j]] = j;
int currWS = j - i + 1;
maxWS = Math.Max(maxWS, currWS);
}
return maxWS;
}
}
