Pular para o conteúdo principal

Longest Substring Without Repeating Characters

Given a string s, return the length of the longest substring that contains only unique characters.

Note: A substring is a contiguous sequence of characters within a string. All characters in the substring must be unique (no duplicates).

Example(s)​

Example 1:

Input: s = "ababbc"
Output: 2
Explanation:
Substrings with unique characters:
- "ab" (length 2)
- "ba" (length 2)
- "bc" (length 2)
The longest has length 2.

Example 2:

Input: s = "abcdssa"
Output: 5
Explanation:
The longest substring with unique characters is "abcds" (length 5).
Other substrings:
- "bcdssa" has duplicate 's'
- "cdssa" has duplicate 's'
- "abcds" is the longest unique substring

Example 3:

Input: s = "abcabcbb"
Output: 3
Explanation:
The longest substring is "abc" (length 3).

Example 4:

Input: s = "bbbbb"
Output: 1
Explanation:
The longest substring is "b" (length 1).

Example 5:

Input: s = "pwwkew"
Output: 3
Explanation:
The longest substring is "wke" (length 3).

Solution​

The solution uses the sliding window technique with a hash set:

  1. Two pointers: Use left and right pointers to define the window
  2. Hash set: Track characters currently in the window
  3. Expand window: Move right pointer and add characters to the set
  4. Shrink window: If duplicate found, move left pointer until duplicate is removed
  5. Track maximum: Keep track of the maximum window size seen

JavaScript Solution - Sliding Window

/**
* Find length of longest substring without repeating characters
* @param {string} s - Input string
* @return {number} - Length of longest unique substring
*/
function lengthOfLongestSubstring(s) {
if (!s || s.length === 0) return 0;

const charSet = new Set();
let left = 0;
let maxLength = 0;

// Expand window with right pointer
for (let right = 0; right < s.length; right++) {
  // If character is already in set, shrink window from left
  while (charSet.has(s[right])) {
    charSet.delete(s[left]);
    left++;
  }
  
  // Add current character to set
  charSet.add(s[right]);
  
  // Update maximum length
  maxLength = Math.max(maxLength, right - left + 1);
}

return maxLength;
}

// Test cases
console.log('Example 1:', lengthOfLongestSubstring("ababbc")); // 2
console.log('Example 2:', lengthOfLongestSubstring("abcdssa")); // 5
console.log('Example 3:', lengthOfLongestSubstring("abcabcbb")); // 3
console.log('Example 4:', lengthOfLongestSubstring("bbbbb")); // 1
console.log('Example 5:', lengthOfLongestSubstring("pwwkew")); // 3
console.log('Test 6:', lengthOfLongestSubstring("")); // 0
console.log('Test 7:', lengthOfLongestSubstring("dvdf")); // 3
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (Hash Map with Index)​

Here's an optimized version using a hash map to store the last index of each character:

/**
 * Optimized: Use hash map to store last index
 * This avoids the while loop in some cases
 */
function lengthOfLongestSubstringOptimized(s) {
  if (!s || s.length === 0) return 0;
  
  const charMap = new Map(); // character -> last index
  let left = 0;
  let maxLength = 0;
  
  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    
    // If character seen before and within current window
    if (charMap.has(char) && charMap.get(char) >= left) {
      // Move left pointer to after the last occurrence
      left = charMap.get(char) + 1;
    }
    
    // Update character's last index
    charMap.set(char, right);
    
    // Update maximum length
    maxLength = Math.max(maxLength, right - left + 1);
  }
  
  return maxLength;
}

Complexity​

  • Time Complexity: O(n) - Where n is the length of the string. Each character is visited at most twice (once by right pointer, once by left pointer).
  • Space Complexity: O(min(n, m)) - Where n is the string length and m is the size of the character set (e.g., 26 for lowercase letters, 128 for ASCII). In the worst case, we store all unique characters.

Approach​

The solution uses the sliding window technique:

  1. Two pointers:

    • left: Start of the current window
    • right: End of the current window (expanding)

  2. Hash set/map:

    • Track characters currently in the window
    • Or track the last index of each character

  3. Expand window:

    • Move right pointer forward
    • Add character to the set

  4. Shrink window:

    • If duplicate found, move left pointer until duplicate is removed
    • Remove characters from set as left moves

  5. Track maximum:

    • Update maximum window size after each expansion

Key Insights​

  • Sliding window: Maintain a window of unique characters
  • Two pointers: Left and right pointers define the window
  • Hash set: Efficient O(1) lookup for checking duplicates
  • Hash map optimization: Can jump left directly to after last occurrence
  • O(n) time: Each character visited at most twice

Step-by-Step Example​

Let's trace through Example 1: s = "ababbc"

Initial: left = 0, right = 0, charSet = {}, maxLength = 0

right = 0: s[0] = 'a'
  charSet.has('a')? No
  charSet.add('a') → {'a'}
  maxLength = max(0, 0-0+1) = 1

right = 1: s[1] = 'b'
  charSet.has('b')? No
  charSet.add('b') → {'a', 'b'}
  maxLength = max(1, 1-0+1) = 2

right = 2: s[2] = 'a'
  charSet.has('a')? Yes
    while loop: remove s[left] = 'a', left = 1
    charSet.has('a')? No (removed)
  charSet.add('a') → {'b', 'a'}
  maxLength = max(2, 2-1+1) = 2

right = 3: s[3] = 'b'
  charSet.has('b')? Yes
    while loop: remove s[left] = 'b', left = 2
    charSet.has('b')? No (removed)
  charSet.add('b') → {'a', 'b'}
  maxLength = max(2, 3-2+1) = 2

right = 4: s[4] = 'b'
  charSet.has('b')? Yes
    while loop: remove s[left] = 'a', left = 3
    charSet.has('b')? Yes
      remove s[left] = 'b', left = 4
    charSet.has('b')? No (removed)
  charSet.add('b') → {'b'}
  maxLength = max(2, 4-4+1) = 2

right = 5: s[5] = 'c'
  charSet.has('c')? No
  charSet.add('c') → {'b', 'c'}
  maxLength = max(2, 5-4+1) = 2

Final: maxLength = 2

Let's trace through Example 2: s = "abcdssa"

Key moments:
- right = 0-4: "abcds" → length 5, maxLength = 5
- right = 5: 's' is duplicate
  - Remove 'a', 'b', 'c', 'd' until 's' removed
  - Window becomes "s"
- right = 6: 's' is duplicate again
  - Remove 's', window becomes "a"
- Final: maxLength = 5

Visual Representation​

Example 1: s = "ababbc"

Window expansion:
a          → length 1
ab         → length 2 ✓
 ba        → length 2 ✓
  ab       → length 2 ✓
   b       → length 1
    bc     → length 2 ✓

Maximum: 2

Edge Cases​

  • Empty string: Return 0
  • Single character: Return 1
  • All same character: Return 1
  • All unique characters: Return string length
  • No duplicates: Return string length
  • Repeated pattern: Find the longest unique segment

Important Notes​

  • Substring vs subsequence: Substring must be contiguous
  • Unique characters: No character can appear twice in the substring
  • Sliding window: Efficiently maintains valid window
  • Hash set/map: Fast duplicate detection
  • Two pointers: Both move forward, never backward

Comparison of Approaches​

ApproachTimeSpaceNotes
Hash SetO(n)O(min(n,m))Simple, clear logic
Hash MapO(n)O(min(n,m))Can jump left pointer directly
  • Longest Substring with At Most K Distinct Characters: Similar sliding window
  • Minimum Window Substring: Different constraint
  • Longest Repeating Character Replacement: Allowing replacements
  • Substring with Concatenation: More complex pattern

Takeaways​

  • Sliding window is the key technique for substring problems
  • Two pointers efficiently maintain a valid window
  • Hash set/map provides fast duplicate detection
  • O(n) time is optimal (each character visited at most twice)
  • Window shrinking handles duplicates efficiently