Longest Substring Without Repeating Characters

• medium
• two pointers
• hash table
• Problem URL

Given a string s, find the length of the longest substring without repeating characters.

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Solution

Use two pointers to keep track of the current substring. Use a map to keep track of the last seen index of each character. If the current character is already in the map and the last seen index of the character is greater than or equal to the left pointer, move the left pointer to the last seen index of the character + 1. Update the last seen index of the character. Update the max length of the substring.

Implementation

Go

func lengthOfLongestSubstring(s string) int {
    m := make(map[rune]int)
    var start, maxLen int

    for end, c := range s {
        val, ok := m[c]
        if ok && val >= start {
            start = val + 1
        }
        m[c] = end
        // max() requires Go 1.21 or later
        maxLen = max(maxLen, end - start + 1)
    }
    return maxLen

}

JavaScript

function lengthOfLongestSubstring(s) {
  const map = new Map();
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    if (map.has(char) && map.get(char) >= left) {
      left = map.get(char) + 1;
    }
    map.set(char, right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

TypeScript

function lengthOfLongestSubstring(s: string): number {
  const map = new Map<string, number>();
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    if (map.has(char) && map.get(char) >= left) {
      left = map.get(char) + 1;
    }
    map.set(char, right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

Pseudocode

1. Create a map to keep track of the last seen index of each character.
2. Create two pointers, left and right to keep track of the current substring.
3. Loop through the string from left to right.
   1. If the current character is already in the map and the last seen index of the character is greater than or equal to the left pointer, move the left pointer to the last seen index of the character + 1.
   2. Update the last seen index of the character.
   3. Update the max length of the substring.
4. Return the max length of the substring.