Approach Summary
Use a sliding window with a hash set. Expand right; when a duplicate is found, shrink from the left until the window is valid again.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Sliding Window with Frequency Map | O(n) | O(min(n, m)) | Maintain frequency counts of characters in the window; shrink left whenever map.size() < window length. |
| 2 Approach 2: Sliding Window with Hash Set (Optimal) | O(n) | O(min(n, m)) | Track distinct characters in a set, advancing left pointer until duplicate is removed. |
Step 1: Baseline
Approach 1: Sliding Window with Frequency Map
Time: O(n)
Space: O(min(n, m))
Track character counts in a hash map. When right advances, increment map[s[right]]. If the number of distinct keys in the map equals the window size (j - i + 1), all characters are unique, so record the maximum length. If map.size() < (j - i + 1), duplicates exist: decrement map[s[left]] and advance left until map.size() matches window length again.
Approach 1: Sliding Window with Frequency Map Implementation
Approach 1: Sliding Window with Frequency Map
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Map<Character, Integer> map = new HashMap<>();
int j = 0, i = 0, maxVal = 0;
while (j < n) {
map.put(s.charAt(j), map.getOrDefault(s.charAt(j), 0) + 1);
if (map.size() == j - i + 1) {
maxVal = Math.max(maxVal, j - i + 1);
j++;
} else if (map.size() < j - i + 1) {
while (map.size() < j - i + 1) {
map.put(s.charAt(i), map.get(s.charAt(i)) - 1);
if (map.get(s.charAt(i)) == 0) {
map.remove(s.charAt(i));
}
i++;
}
if (map.size() == j - i + 1) {
maxVal = Math.max(maxVal, j - i + 1);
}
j++;
}
}
return maxVal;
}
}class Solution {
public:
int lengthOfLongestSubstring(string s) {
int i = 0, j = 0, n = s.size(), maxLen = 0;
unordered_map<char, int> m;
while (j < n) {
m[s[j]]++;
if (m.size() == j - i + 1) {
maxLen = max(maxLen, j - i + 1);
j++;
} else if (m.size() < j - i + 1) {
while (m.size() < j - i + 1) {
m[s[i]]--;
if (m[s[i]] == 0) m.erase(s[i]);
i++;
}
if (m.size() == j - i + 1) {
maxLen = max(maxLen, j - i + 1);
}
j++;
}
}
return maxLen;
}
};class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
freq = {}
i, j = 0, 0
n = len(s)
max_len = 0
while j < n:
freq[s[j]] = freq.get(s[j], 0) + 1
if len(freq) == j - i + 1:
max_len = max(max_len, j - i + 1)
j += 1
elif len(freq) < j - i + 1:
while len(freq) < j - i + 1:
freq[s[i]] -= 1
if freq[s[i]] == 0:
del freq[s[i]]
i += 1
if len(freq) == j - i + 1:
max_len = max(max_len, j - i + 1)
j += 1
return max_lenfunction lengthOfLongestSubstring(s) {
const n = s.length;
const map = new Map();
let i = 0, j = 0, maxVal = 0;
while (j < n) {
map.set(s[j], (map.get(s[j]) || 0) + 1);
if (map.size === j - i + 1) {
maxVal = Math.max(maxVal, j - i + 1);
j++;
} else if (map.size < j - i + 1) {
while (map.size < j - i + 1) {
map.set(s[i], map.get(s[i]) - 1);
if (map.get(s[i]) === 0) map.delete(s[i]);
i++;
}
if (map.size === j - i + 1) {
maxVal = Math.max(maxVal, j - i + 1);
}
j++;
}
}
return maxVal;
} Step 2: Most Optimized
Approach 2: Sliding Window with Hash Set (Optimal)
Time: O(n)
Space: O(min(n, m))
Maintain two pointers left and right and an active character set. If s[right] is not in the set, insert it, update maxLen, and increment right. If s[right] is already in the set, remove s[left] and increment left without advancing right until the duplicate character has been evicted.
Approach 2: Sliding Window with Hash Set (Optimal) Implementation
Approach 2: Sliding Window with Hash Set (Optimal)
class Solution {
public int lengthOfLongestSubstring(String s) {
int left = 0, right = 0, n = s.length(), maxLen = 0;
Set<Character> uniqueCharacters = new HashSet<>();
while (right < n) {
if (!uniqueCharacters.contains(s.charAt(right))) {
uniqueCharacters.add(s.charAt(right));
maxLen = Math.max(maxLen, right - left + 1);
right++;
} else {
uniqueCharacters.remove(s.charAt(left));
left++;
}
}
return maxLen;
}
}class Solution {
public:
int lengthOfLongestSubstring(string s) {
int maxLen = 0, left = 0, right = 0, n = s.size();
unordered_set<char> uniqueCharacters;
while (right < n) {
if (uniqueCharacters.find(s[right]) == uniqueCharacters.end()) {
uniqueCharacters.insert(s[right]);
maxLen = max(maxLen, right - left + 1);
right++;
} else {
uniqueCharacters.erase(s[left]);
left++;
}
}
return maxLen;
}
};class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
char_set = set()
left = 0
max_len = 0
for right in range(len(s)):
while s[right] in char_set:
char_set.remove(s[left])
left += 1
char_set.add(s[right])
max_len = max(max_len, right - left + 1)
return max_lenfunction lengthOfLongestSubstring(s) {
const charSet = new Set();
let left = 0, maxLen = 0;
for (let right = 0; right < s.length; right++) {
while (charSet.has(s[right])) {
charSet.delete(s[left]);
left++;
}
charSet.add(s[right]);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}Edge Cases to Watch
- Empty string "" (returns 0)
- String with all identical characters "bbbbb" (returns 1)
- String with all unique characters "abcdef" (returns len(s))
- String with space and special characters (e.g. "pwwkew" or "abc def")
Algorithmic Pattern
View Pattern Guide →
Master the Sliding Window Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Sliding Window pattern.
Framework: Sliding Window • Interview Prep: Tested at FAANG •
Explore all Sliding Window problems & invariants →
How to Recognize This Pattern
- Asks for longest substring
- Unique character constraint
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(min(n, alphabet))
Tags
String Hash Map Sliding Window
Frequently Asked Questions
What is the optimal time and space complexity for Longest Substring Without Repeating Characters?
The optimal solution for Longest Substring Without Repeating Characters achieves O(n) runtime complexity and requires O(min(n, alphabet)) auxiliary space. Time complexity is O(n) because each character is visited at most twice (once by right pointer and once by left pointer). Space complexity is O(min(n, m)) where m is the size of the alphabet/character set (at most 256 for ASCII or 26 for English letters).
How do I identify that Longest Substring Without Repeating Characters requires the Sliding Window pattern?
In technical interviews, look for key problem signals: Asks for longest substring; Unique character constraint. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Sliding Window strategy.
What critical edge cases must be handled in Longest Substring Without Repeating Characters?
Essential edge cases to verify include: Empty string "" (returns 0); String with all identical characters "bbbbb" (returns 1); String with all unique characters "abcdef" (returns len(s)); String with space and special characters (e.g. "pwwkew" or "abc def"). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Longest Substring Without Repeating Characters?
Longest Substring Without Repeating Characters is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Google, Facebook, Microsoft.