Write a function `longestUniqueSubstring(str)` that returns the length of the longest substring without repeating characters.
Problem Statement
<p>Write a function <code>longestUniqueSubstring(str)</code> that returns the length of the longest substring without repeating characters.</p>
Examples
Input: str = "abcabcbb"
Output: 3
Explanation: The answer is "abc" with length 3.
Input: str = "bbbbb"
Output: 1
Explanation: The answer is "b" with length 1.
Complexity
Time Complexity: O(N)
Space Complexity: O(1)
Hints
š” Hint 1:
Use the sliding window technique with two pointers.
š” Hint 2:
Use a Set to track characters in the current window.
š” Hint 3:
When a duplicate is found, shrink the window from the left until the duplicate is removed.
Editorial & Approach
Problem Overview & Intuition
To solve Longest Substring Without Repeating Characters, we consider the execution characteristics of JavaScript engines. Write a function `longestUniqueSubstring(str)` that returns the length of the longest substring without repeating characters. By utilizing idiomatic language constructs and clean algorithmic principles, we can accomplish this with optimal time and memory usage.
Step-by-Step Approach
- Understand Problem Contract: Identify input arguments, return type expectations, and edge cases (empty inputs, nullish values).
- Choose Core Mechanism: Use modern JavaScript patterns (use the sliding window technique with two pointers).
- Implement Logic: Handle state and transformations efficiently (use a set to track characters in the current window).
- Return Result: Ensure proper return format and preserve caller context if applicable.
Optimal Implementation (JavaScript)
function longestUniqueSubstring(str) {
const seen = new Set();
let left = 0;
let max = 0;
for (let right = 0; right < str.length; right++) {
while (seen.has(str[right])) {
seen.delete(str[left]);
left++;
}
seen.add(str[right]);
max = Math.max(max, right - left + 1);
}
return max;
}Complexity Analysis
Time Complexity
O(N) linear scan over input
Space Complexity
O(1) constant auxiliary space (or O(N) output)
Edge Cases & Corner Traps Handled
- Empty or boundary inputs (empty arrays, strings, zero length).
- Type checks and unexpected values (e.g.
null,undefined, negative numbers). - Closure preservation and memory isolation between separate invocations.