🎨Now live: Try our Free AI Image Generation Feature

Intuition
To find the length of the longest substring without repeating characters, we can use a sliding window approach. This allows us to efficiently manage the window of characters currently being considered and quickly adjust when we encounter a repeating character.
Approach
- Initialize Variables:
-
char_map
: A dictionary to store the latest index of each character. -max_length
: An integer to keep track of the maximum length of substrings found. -start
: An integer to mark the starting index of the current window of characters. - Sliding Window Technique:
- Iterate through the string using a variable
end
as the end index of the current window. - For each character at indexend
: - If the character is already inchar_map
, updatestart
to the maximum ofstart
and the index after the last occurrence of the character. This effectively shrinks the window from the left to remove the repeating character. - Updatechar_map
with the current indexend
for the character. - Updatemax_length
to the maximum ofmax_length
and the length of the current window (end - start + 1
). - Return Result:
- After iterating through the string, return
max_length
, which contains the length of the longest substring without repeating characters.
Complexity
Time Complexity:
O(n), where n
is the length of the string. Each character is processed at most twice (once by the end
pointer and once by the start
pointer).
Space Complexity:
O(min(m, n)), where m
is the size of the character set and n
is the length of the string. This is because the dictionary will store at most min(m, n)
characters.
Code
C++
#include
#include
#include
using namespace std;
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.length();
if (n == 0) return 0;
unordered_map map;
int maxLength = 0;
int start = 0;
for (int end = 0; end < n; end++) {
char c = s[end];
if (map.find(c) != map.end()) {
start = max(start, map[c] + 1);
}
map[c] = end;
maxLength = max(maxLength, end - start + 1);
}
return maxLength;
}
};
Python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
n = len(s)
if n == 0:
return 0
char_map = {}
max_length = 0
start = 0
for end in range(n):
if s[end] in char_map:
start = max(start, char_map[s[end]] + 1)
char_map[s[end]] = end
max_length = max(max_length, end - start + 1)
return max_length
Java
import java.util.HashMap;
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
if (n == 0) return 0;
HashMap map = new HashMap<>();
int maxLength = 0;
int start = 0;
for (int end = 0; end < n; end++) {
char c = s.charAt(end);
if (map.containsKey(c)) {
start = Math.max(start, map.get(c) + 1);
}
map.put(c, end);
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}
}
JavaScript
var lengthOfLongestSubstring = function(s) {
const n = s.length;
if (n === 0) return 0;
const charMap = new Map();
let maxLength = 0;
let start = 0;
for (let end = 0; end < n; end++) {
if (charMap.has(s[end])) {
start = Math.max(start, charMap.get(s[end]) + 1);
}
charMap.set(s[end], end);
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
};