Unique Characters Substring — Problem Statement & Solution Guide
Problem Description
You are given a string s. Your task is to determine the length of the longest contiguous substring that contains no repeated characters. The substring must be a continuous segment of s; characters may appear only once within that segment. The result should be a single integer representing that maximum length.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Unique Characters Substring"
WHY DOES IT MATTER?
The sliding‑window pattern is essential for any problem that asks for an optimal contiguous segment under a dynamic constraint, because it avoids recomputation by reusing previous work as the window slides.
OPTIMIZATION CHALLENGE
The key insight is to store the last seen index of each character, allowing the left boundary to jump directly to the position after the previous duplicate instead of moving one step at a time, which collapses the quadratic worst case to linear.
REAL-WORLD CONNECTION
Think of a network packet inspector that continuously scans a data stream for a sequence of unique identifiers; the inspector slides its inspection window forward, discarding old packets as soon as a duplicate identifier appears, ensuring real‑time detection without buffering the entire stream.
During an interview, write the hash‑map update and left‑pointer adjustment in a single line inside the loop; this demonstrates both clarity and mastery of the sliding‑window invariant.
COMPLEXITY AT A GLANCE
O(n)O(min(n, m))Core Theory — Why This Approach?
The longest substring without repeating characters is a classic sliding‑window problem that leverages the concept of a dynamic interval over the input string. By maintaining two pointers—left and right—that delimit the current window, we can expand the window to include new characters while ensuring the invariant that all characters inside are unique. When a duplicate is encountered, the left pointer is advanced just past the previous occurrence of that character, effectively discarding the conflicting portion of the window. This approach transforms the problem from an O(n²) exhaustive search into a linear scan because each character is visited at most twice (once when the right pointer moves forward and once when the left pointer catches up).
Naïve solutions typically generate every possible substring and check for duplicates using a set or nested loops, leading to quadratic time complexity that quickly becomes prohibitive for strings of length 10⁵ or more. The optimal paradigm—sliding window combined with a hash map (or an array for fixed alphabets)—stores the most recent index of each character, enabling O(1) look‑ups to decide whether the current character violates the uniqueness constraint. This data‑driven window adjustment is the cornerstone of many “longest subarray/subsequence with constraints” problems across competitive programming and real‑world systems.
Interview Questions on This Problem
Q1How would you modify the sliding‑window solution if the input string could contain Unicode characters beyond the ASCII range?
Use a hash map (e.g., unordered_map<char32_t, int> in C++ or a dict in Python) to store the last index of each Unicode code point instead of a fixed‑size array; the rest of the algorithm remains unchanged because look‑ups stay O(1) on average.
Q2Can you adapt the algorithm to return the actual longest substring, not just its length, and what additional space does this require?
Track the start index of the best window whenever a longer length is found; after the scan, slice the original string from bestStart to bestStart+maxLen. This adds O(1) extra variables, so space remains O(1) beyond the hash map.
Q3Explain how you would solve the problem if the constraint changed to "at most K distinct characters" instead of "no repeats".
Maintain a frequency map of characters inside the window and a counter of distinct characters. Expand the right pointer, increment frequencies, and when distinctCount exceeds K, shrink the left pointer while decrementing frequencies until distinctCount ≤ K. This still runs in O(n) time with O(K) space.
Examples
Input
abca
Output
3
Explanation: Scan the string from left to right. The first three characters 'a','b','c' form a substring with all unique characters, giving length 3. Adding the next character 'a' would repeat a character, so the longest unique substring ending at that point is still length 3. No longer unique substring exists in the string, so the answer is 3.
Input
abcd
Output
4
Explanation: Each character in 'abcd' is distinct, so the entire string is a unique substring. Its length is 4, which is the maximum possible for this input.
Input
aab
Output
2
Explanation: Starting at the first character, the substring 'aa' contains a repeated 'a', so the longest unique substring starting there is just 'a' (length 1). Moving to the second character, the substring 'ab' has no repeats and length 2. No longer unique substring exists, so the answer is 2.
Constraints
- 1 <= s.length <= 100000
- s consists of printable ASCII characters (codes 32 to 126)
Optimal Approach & Strategy
Use a sliding window with a hash map that records the latest index of each character, moving the left pointer forward only when a duplicate is encountered.
Brute Force Approach
Generate every possible substring and check each for duplicate characters using a set; keep the maximum length found.
Verified Code Solutions
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
const lastSeen = new Map();
let left = 0;
let maxLen = 0;
for (let right = 0; right < s.length; right++) {
const char = s[right];
if (lastSeen.has(char) && lastSeen.get(char) >= left) {
left = lastSeen.get(char) + 1;
}
lastSeen.set(char, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
};class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> lastSeen;
int left = 0;
int maxLen = 0;
for (int right = 0; right < s.size(); ++right) {
if (lastSeen.find(s[right]) != lastSeen.end() && lastSeen[s[right]] >= left) {
left = lastSeen[s[right]] + 1;
}
lastSeen[s[right]] = right;
maxLen = max(maxLen, right - left + 1);
}
return maxLen;
}
};class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> lastSeen = new HashMap<>();
int left = 0;
int maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) {
left = lastSeen.get(c) + 1;
}
lastSeen.put(c, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
}class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
last_seen = {}
left = 0
max_len = 0
for right, char in enumerate(s):
if char in last_seen and last_seen[char] >= left:
left = last_seen[char] + 1
last_seen[char] = right
max_len = max(max_len, right - left + 1)
return max_len/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
const lastSeen = new Map();
let left = 0;
let maxLen = 0;
for (let right = 0; right < s.length; right++) {
const char = s[right];
if (lastSeen.has(char) && lastSeen.get(char) >= left) {
left = lastSeen.get(char) + 1;
}
lastSeen.set(char, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
};Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.