Longest Substring Without Repeating Characters

medium
Sliding WindowStringSliding WindowHash Table

Given a string s, find the length of the longest substring without repeating characters. A substring is a contiguous sequence of characters within the string, and every character in the substring must be unique.

Examples

Example 1

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

Example 2

  • Input: s = "bbbbb"
  • Output: 1
  • Explanation: The answer is "b", with the length of 1.

Example 3

  • Input: s = "pwwkew"
  • Output: 3
  • Explanation: The answer is "wke", with the length of 3. Note that "pwke" is a subsequence, not a substring.

Constraints

  • 0 <= s.length <= 5 * 10^4
  • s consists of English letters, digits, symbols, and spaces.

Approaches

3 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Brute Force

Intuition

The most straightforward approach is to examine every possible substring and check if it contains all unique characters. For each starting index, we extend the substring one character at a time and use a set to track characters we have seen. If a duplicate is found, we stop extending. We track the maximum length across all valid substrings.

Algorithm

  1. Initialize maxLen to 0.
  2. For each starting index i from 0 to n - 1, create an empty set.
  3. For each ending index j starting from i, check if s[j] is already in the set.
  4. If s[j] is in the set, break out of the inner loop.
  5. Otherwise, add s[j] to the set and update maxLen with the current window size j - i + 1.
  6. Return maxLen.
TimeO(n^2)SpaceO(min(n, m)) where m is the character set size

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int maxLen = 0;
        int n = s.size();

        for (int i = 0; i < n; i++) {
            unordered_set<char> seen;
            for (int j = i; j < n; j++) {
                if (seen.count(s[j])) break;
                seen.insert(s[j]);
                maxLen = max(maxLen, j - i + 1);
            }
        }

        return maxLen;
    }
};
Java 21
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLen = 0;
        int n = s.length();

        for (int i = 0; i < n; i++) {
            Set<Character> seen = new HashSet<>();
            for (int j = i; j < n; j++) {
                if (seen.contains(s.charAt(j))) break;
                seen.add(s.charAt(j));
                maxLen = Math.max(maxLen, j - i + 1);
            }
        }

        return maxLen;
    }
}
Python 3.12
def lengthOfLongestSubstring(s: str) -> int:
    max_len = 0
    n = len(s)

    for i in range(n):
        seen = set()
        for j in range(i, n):
            if s[j] in seen:
                break
            seen.add(s[j])
            max_len = max(max_len, j - i + 1)

    return max_len
Go 1.26
func lengthOfLongestSubstring(s string) int {
    maxLen := 0
    n := len(s)

    for i := 0; i < n; i++ {
        seen := make(map[byte]bool)
        for j := i; j < n; j++ {
            if seen[s[j]] {
                break
            }
            seen[s[j]] = true
            if j-i+1 > maxLen {
                maxLen = j - i + 1
            }
        }
    }

    return maxLen
}
Approach 2

Sliding Window with Hash Set

Intuition

We maintain a window [left, right] that always contains unique characters. We use a hash set to track characters in the current window. When we encounter a duplicate at the right pointer, we shrink the window from the left by removing characters until the duplicate is gone. This way each character is added and removed from the set at most once, giving us linear time.

Algorithm

  1. Initialize a hash set and two pointers: left = 0 and right = 0.
  2. While right < n, check if s[right] is in the set.
  3. If s[right] is not in the set, add it and update the maximum length as right - left + 1, then increment right.
  4. If s[right] is in the set, remove s[left] from the set and increment left.
  5. Return the maximum length.
TimeO(n)SpaceO(min(n, m)) where m is the character set size

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> seen;
        int maxLen = 0;
        int left = 0;

        for (int right = 0; right < s.size(); right++) {
            while (seen.count(s[right])) {
                seen.erase(s[left]);
                left++;
            }
            seen.insert(s[right]);
            maxLen = max(maxLen, right - left + 1);
        }

        return maxLen;
    }
};
Java 21
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> seen = new HashSet<>();
        int maxLen = 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));
            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}
Python 3.12
def lengthOfLongestSubstring(s: str) -> int:
    seen = set()
    max_len = 0
    left = 0

    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        max_len = max(max_len, right - left + 1)

    return max_len
Go 1.26
func lengthOfLongestSubstring(s string) int {
    seen := make(map[byte]bool)
    maxLen := 0
    left := 0

    for right := 0; right < len(s); right++ {
        for seen[s[right]] {
            delete(seen, s[left])
            left++
        }
        seen[s[right]] = true
        if right-left+1 > maxLen {
            maxLen = right - left + 1
        }
    }

    return maxLen
}
Approach 3

Sliding Window with Hash Map (Optimized)

Intuition

Instead of shrinking the window one character at a time, we can use a hash map that stores the last seen index of each character. When a duplicate is found, we jump the left pointer directly past the previous occurrence of that character. This avoids redundant removals and processes each character exactly once with a single pass.

Algorithm

  1. Create a hash map to store the most recent index of each character.
  2. Initialize left = 0 and maxLen = 0.
  3. For each index right from 0 to n - 1, check if s[right] is in the map and its stored index is >= left.
  4. If so, move left to map[s[right]] + 1 to skip past the previous occurrence.
  5. Update map[s[right]] to right.
  6. Update maxLen as max(maxLen, right - left + 1).
  7. Return maxLen.
TimeO(n)SpaceO(min(n, m)) where m is the character set size

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> lastIndex;
        int maxLen = 0;
        int left = 0;

        for (int right = 0; right < s.size(); right++) {
            if (lastIndex.count(s[right]) && lastIndex[s[right]] >= left) {
                left = lastIndex[s[right]] + 1;
            }
            lastIndex[s[right]] = right;
            maxLen = max(maxLen, right - left + 1);
        }

        return maxLen;
    }
};
Java 21
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> lastIndex = new HashMap<>();
        int maxLen = 0;
        int left = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (lastIndex.containsKey(c) && lastIndex.get(c) >= left) {
                left = lastIndex.get(c) + 1;
            }
            lastIndex.put(c, right);
            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}
Python 3.12
def lengthOfLongestSubstring(s: str) -> int:
    last_index = {}
    max_len = 0
    left = 0

    for right in range(len(s)):
        if s[right] in last_index and last_index[s[right]] >= left:
            left = last_index[s[right]] + 1
        last_index[s[right]] = right
        max_len = max(max_len, right - left + 1)

    return max_len
Go 1.26
func lengthOfLongestSubstring(s string) int {
    lastIndex := make(map[byte]int)
    maxLen := 0
    left := 0

    for right := 0; right < len(s); right++ {
        if idx, ok := lastIndex[s[right]]; ok && idx >= left {
            left = idx + 1
        }
        lastIndex[s[right]] = right
        if right-left+1 > maxLen {
            maxLen = right - left + 1
        }
    }

    return maxLen
}

Frequently asked questions

What is the optimal time complexity of Longest Substring Without Repeating Characters?

The most efficient approach in this guide ("Sliding Window with Hash Map (Optimized)") runs in O(n) time and uses O(min(n, m)) where m is the character set size extra space. Earlier brute-force approaches are slower; see all 3 approaches above for the full progression.

What pattern does Longest Substring Without Repeating Characters use?

Longest Substring Without Repeating Characters is a medium-level Sliding Window problem involving String, Sliding Window, Hash Table. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Longest Substring Without Repeating Characters be solved without extra space?

The most space-efficient approach in this guide uses O(min(n, m)) where m is the character set size extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(min(n, m)) where m is the character set size, while the optimized version uses O(min(n, m)) where m is the character set size.

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Longest Repeating Character Replacement

Original problem: leetcode.com

Loading editor...
Input
s=
"abcabcbb"
Expected Output
3