17. Longest Substring Without Repeating Characters · DSA Practice

Return the length of the longest substring (contiguous) of s in which no character repeats.

Example 1

Input: s = "abcabcbb"

Output: 3

Explanation: “abc” is the longest such substring.

Example 2

Input: s = "abba"

Output: 2

Constraints

0 ≤ s.length ≤ 5·10⁴

Hint 1

Grow a window to the right; when a character repeats, move the left edge just past its previous position.

Sliding WindowHash TableString

Approach 1: Check every substring

For each start, extend until a repeat.

⏱ Time O(n²)💾 Space O(k)

Approach 2: Sliding window + last index ✅

Store the last index of each character and jump left past repeats.

⏱ Time O(n)💾 Space O(k)

Reference solution for Sliding window + last index (time O(n), space O(k)). Each solution passes every test in all four languages.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last = {}                 # char -> last index seen
        left = best = 0
        for right, ch in enumerate(s):
            if ch in last and last[ch] >= left:
                left = last[ch] + 1    # jump past the previous copy
            last[ch] = right
            best = max(best, right - left + 1)
        return best

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> last = new HashMap<>();
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            Integer p = last.get(ch);
            if (p != null && p >= left) left = p + 1;
            last.put(ch, right);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> last(256, -1);
        int left = 0, best = 0;
        for (int right = 0; right < (int)s.size(); right++) {
            unsigned char ch = s[right];
            if (last[ch] >= left) left = last[ch] + 1;
            last[ch] = right;
            best = max(best, right - left + 1);
        }
        return best;
    }
};

function lengthOfLongestSubstring(s) {
  const last = new Map();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    if (last.has(ch) && last.get(ch) >= left) left = last.get(ch) + 1;
    last.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Sliding Window.