Dare2Solve
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.
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 index end
:
If the character is already in char_map
, update start
to the maximum of start
and the index after the last occurrence of the character. This effectively shrinks the window from the left to remove the repeating character.
Update char_map
with the current index end
for the character.
Update max_length
to the maximum of max_length
and the length of the current window (end - start + 1
).
Return Result:
max_length
, which contains the length of the longest substring without repeating characters.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).
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.
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.length();
if (n == 0) return 0;
unordered_map<char, int> 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;
}
};
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
import java.util.HashMap;
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
if (n == 0) return 0;
HashMap<Character, Integer> 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;
}
}
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;
};