Solutions

1. Brute Force

O(n²) time | O(n) space

Intuition

We can take every character and find the longest substring without repeating characters when that character is a start of a substring, keeping the greatest length.

Algorithm

Create an integer variable longest with initial value 0.
Iterate through the outer loop from the first character to the last character with i index.
For each outer loop iteration, create an empty hash set and iterate through the inner loop from the character at i to the last character with j index.
- Leave the inner loop if the character at j is in the hash set.
- Otherwise add the character to the hash set and update longest with j - i + 1 if it is greater.
Return longest.

012345

p is new. length = 1, longest = 1

1 / 16

Code

def lengthOfLongestSubstring(s: str) -> int:
    longest = 0
    for i in range(len(s)):
        seen = set()
        for j in range(i, len(s)):
            if s[j] in seen:
                break
            seen.add(s[j])
            longest = max(longest, j - i + 1)
    return longest

/**
 * @param {string} s
 * @returns {number}
 */
var lengthOfLongestSubstring = function (s) {
  let longest = 0
  for (let i = 0; i < s.length; i++) {
    const seen = new Set()
    for (let j = i; j < s.length; j++) {
      if (seen.has(s[j])) break
      seen.add(s[j])
      longest = Math.max(longest, j - i + 1)
    }
  }
  return longest
}

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int longest = 0;
        for (int i = 0; i < s.length(); i++) {
            Set<Character> seen = new HashSet<>();
            for (int j = i; j < s.length(); j++) {
                if (seen.contains(s.charAt(j))) break;
                seen.add(s.charAt(j));
                longest = Math.max(longest, j - i + 1);
            }
        }
        return longest;
    }
}

2. Sliding Window

O(n) time | O(n) space

Intuition

We can keep one substring as a window between the left and right indexes, and extend it by moving right one character forward.

When the character at right is already inside the window, we move left forward until it is gone.

When we move right forward, left never goes back towards the start, because we know that every window that starts before it contains a repeated character.

Then at every right index the window is the longest substring without repeating characters that ends there.

Algorithm

Create an empty hash set and a longest integer variable with initial value 0.
Create a left index variable with initial value 0.
Iterate through the loop from the first character to the last character with right index.
- While the character at right is in the hash set, remove the character at left from the hash set and move left one step to the right.
- Add the character at right to the hash set and update longest with right - left + 1 if it is greater.
Return longest.

012345

leftright

p is new. length = 1, longest = 1

1 / 10

Code

def lengthOfLongestSubstring(s: str) -> int:
    seen = set()
    longest = 0
    left = 0
    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        longest = max(longest, right - left + 1)
    return longest

/**
 * @param {string} s
 * @returns {number}
 */
var lengthOfLongestSubstring = function (s) {
  const seen = new Set()
  let longest = 0
  let left = 0
  for (let right = 0; right < s.length; right++) {
    while (seen.has(s[right])) {
      seen.delete(s[left])
      left++
    }
    seen.add(s[right])
    longest = Math.max(longest, right - left + 1)
  }
  return longest
}

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> seen = new HashSet<>();
        int longest = 0;
        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            while (seen.contains(s.charAt(right))) {
                seen.remove(s.charAt(left));
                left++;
            }
            seen.add(s.charAt(right));
            longest = Math.max(longest, right - left + 1);
        }
        return longest;
    }
}