JavaScript
class Solution {
// Approach using Set
lengthOfLongestSubstring(s) {
let maxLength = 0;
let start = 0;
const seen = new Set();
for (let end = 0; end < s.length; end++) {
while (seen.has(s[end])) {
seen.delete(s[start]);
start++;
}
seen.add(s[end]);
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}
// Time: O(n), Space: O(k)
// Approach using Map
lengthOfLongestSubstringMap(s) {
let maxLength = 0;
let start = 0;
const lastSeen = new Map();
for (let end = 0; end < s.length; end++) {
if (lastSeen.has(s[end])) {
start = Math.max(start, lastSeen.get(s[end]) + 1);
}
lastSeen.set(s[end], end);
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}
// Time: O(n), Space: O(k)
}
Java
class Solution {
// Approach using HashSet
public int lengthOfLongestSubstring(String s) {
int maxLength = 0;
int start = 0;
Set<Character> seen = new HashSet<>();
for (int end = 0; end < s.length(); end++) {
while (seen.contains(s.charAt(end))) {
seen.remove(s.charAt(start));
start++;
}
seen.add(s.charAt(end));
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}
// Time: O(n), Space: O(k)
// Approach using HashMap
public int lengthOfLongestSubstringMap(String s) {
int maxLength = 0;
int start = 0;
Map<Character, Integer> lastSeen = new HashMap<>();
for (int end = 0; end < s.length(); end++) {
char currentChar = s.charAt(end);
if (lastSeen.containsKey(currentChar)) {
start = Math.max(start, lastSeen.get(currentChar) + 1);
}
lastSeen.put(currentChar, end);
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}
// Time: O(n), Space: O(k)
}
Python
class Solution:
# Approach using set
def lengthOfLongestSubstring(self, s: str) -> int:
seen = set()
max_length = start = 0
for end, char in enumerate(s):
while char in seen:
seen.remove(s[start])
start += 1
seen.add(char)
max_length = max(max_length, end - start + 1)
return max_length
# Time: O(n), Space: O(k)
# Approach using dict
def lengthOfLongestSubstring_dict(self, s: str) -> int:
last_seen = {}
max_length = start = 0
for end, char in enumerate(s):
if char in last_seen:
start = max(start, last_seen[char] + 1)
last_seen[char] = end
max_length = max(max_length, end - start + 1)
return max_length
# Time: O(n), Space: O(k)