3. Longest Substring Without Repeating Characters - Explanation

Description

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

A substring is a contiguous sequence of characters within a string.

Example 1:

Input: s = "zxyzxyz"

Output: 3

Explanation: The string "xyz" is the longest without duplicate characters.

Example 2:

Input: s = "xxxx"

Output: 1

Constraints:

0 <= s.length <= 1000
s may consist of printable ASCII characters.

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(m) space, where n is the length of the string and m is the number of unique characters in the string.

Hint 1

A brute force solution would be to try the substring starting at index i and try to find the maximum length we can form without duplicates by starting at that index. We can use a hash set to detect duplicates in O(1) time. Can you think of a better way?

Hint 2

We can use the sliding window algorithm. Since we only care about substrings without duplicate characters, the sliding window can help us maintain valid substring with its dynamic nature.

Hint 3

We can iterate through the given string with index r as the right boundary and l as the left boundary of the window. We use a hash set to check if the character is present in the window or not. When we encounter a character at index r that is already present in the window, we shrink the window by incrementing the l pointer until the window no longer contains any duplicates. Also, we remove characters from the hash set that are excluded from the window as the l pointer moves. At each iteration, we update the result with the length of the current window, r - l + 1, if this length is greater than the current result.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Sliding Window Technique - Used to maintain a window of unique characters that can expand and shrink dynamically
Hash Set - Needed to track which characters are currently in the window for O(1) duplicate detection
Hash Map (optional) - The optimal solution uses a map to store character indices for direct pointer jumps

1. Brute Force

Intuition

The brute-force idea is to try starting a substring at every index and keep extending it until we see a repeated character.
For each starting point, we use a set to track the characters we’ve seen so far.
As soon as a duplicate appears, that substring can’t grow anymore, so we stop and record its length.
By doing this for every index, we are guaranteed to find the longest valid substring, though the approach is slow.

Algorithm

Initialize res = 0 to store the maximum length.
For each starting index i:
- Create an empty set charSet.
- Extend the substring by moving j from i forward:
  - If s[j] is already in the set, break.
  - Otherwise, add it to the set.
- Update res with the size of charSet.
Return res after checking all starting positions.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        res = 0
        for i in range(len(s)):
            charSet = set()
            for j in range(i, len(s)):
                if s[j] in charSet:
                    break
                charSet.add(s[j])
            res = max(res, len(charSet))
        return res

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

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0;
        for (int i = 0; i < s.size(); i++) {
            unordered_set<char> charSet;
            for (int j = i; j < s.size(); j++) {
                if (charSet.find(s[j]) != charSet.end()) {
                    break;
                }
                charSet.insert(s[j]);
            }
            res = max(res, (int)charSet.size());
        }
        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    lengthOfLongestSubstring(s) {
        let res = 0;
        for (let i = 0; i < s.length; i++) {
            let charSet = new Set();
            for (let j = i; j < s.length; j++) {
                if (charSet.has(s[j])) {
                    break;
                }
                charSet.add(s[j]);
            }
            res = Math.max(res, charSet.size);
        }
        return res;
    }
}

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        int res = 0;
        for (int i = 0; i < s.Length; i++) {
            HashSet<char> charSet = new HashSet<char>();
            for (int j = i; j < s.Length; j++) {
                if (charSet.Contains(s[j])) {
                    break;
                }
                charSet.Add(s[j]);
            }
            res = Math.Max(res, charSet.Count);
        }
        return res;
    }
}

func lengthOfLongestSubstring(s string) int {
    res := 0

    for i := 0; i < len(s); i++ {
        charSet := make(map[byte]bool)
        for j := i; j < len(s); j++ {
            if charSet[s[j]] {
                break
            }
            charSet[s[j]] = true
        }
        if len(charSet) > res {
            res = len(charSet)
        }
    }
    return res
}

class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var res = 0
        let chars = Array(s)

        for i in 0..<chars.count {
            var charSet = Set<Character>()
            for j in i..<chars.count {
                if charSet.contains(chars[j]) {
                    break
                }
                charSet.insert(chars[j])
            }
            res = max(res, charSet.count)
        }
        return res
    }
}

impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        let s = s.as_bytes();
        let mut res = 0;

        for i in 0..s.len() {
            let mut char_set = HashSet::new();
            for j in i..s.len() {
                if char_set.contains(&s[j]) {
                    break;
                }
                char_set.insert(s[j]);
            }
            res = res.max(char_set.len());
        }
        res as i32
    }
}

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(m)$

Where $n$ is the length of the string and $m$ is the total number of unique characters in the string.

2. Sliding Window

Intuition

Instead of restarting at every index like brute force, we can keep one window that always has unique characters.
We expand the window by moving the right pointer.
If we ever see a repeated character, we shrink the window from the left until the duplicate is removed.
This way, the window always represents a valid substring, and we track its maximum size.
It's efficient because each character is added and removed at most once.

Algorithm

Create an empty set charSet and two pointers:
- l = left edge of the window
- r = right edge that moves through the string
For each r:
- While s[r] is already in the set:
  - Remove s[l] from the set and move l right.
- Add s[r] to the set.
- Update the result with the window size: r - l + 1.
Return the maximum window size found.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        charSet = set()
        l = 0
        res = 0

        for r in range(len(s)):
            while s[r] in charSet:
                charSet.remove(s[l])
                l += 1
            charSet.add(s[r])
            res = max(res, r - l + 1)
        return res

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashSet<Character> charSet = new HashSet<>();
        int l = 0;
        int res = 0;

        for (int r = 0; r < s.length(); r++) {
            while (charSet.contains(s.charAt(r))) {
                charSet.remove(s.charAt(l));
                l++;
            }
            charSet.add(s.charAt(r));
            res = Math.max(res, r - l + 1);
        }
        return res;
    }
}

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> charSet;
        int l = 0;
        int res = 0;

        for (int r = 0; r < s.size(); r++) {
            while (charSet.find(s[r]) != charSet.end()) {
                charSet.erase(s[l]);
                l++;
            }
            charSet.insert(s[r]);
            res = max(res, r - l + 1);
        }
        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    lengthOfLongestSubstring(s) {
        const charSet = new Set();
        let l = 0;
        let res = 0;

        for (let r = 0; r < s.length; r++) {
            while (charSet.has(s[r])) {
                charSet.delete(s[l]);
                l++;
            }
            charSet.add(s[r]);
            res = Math.max(res, r - l + 1);
        }
        return res;
    }
}

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        HashSet<char> charSet = new HashSet<char>();
        int l = 0;
        int res = 0;

        for (int r = 0; r < s.Length; r++) {
            while (charSet.Contains(s[r])) {
                charSet.Remove(s[l]);
                l++;
            }
            charSet.Add(s[r]);
            res = Math.Max(res, r - l + 1);
        }
        return res;
    }
}

func lengthOfLongestSubstring(s string) int {
    charSet := make(map[byte]bool)
    l, res := 0, 0

    for r := 0; r < len(s); r++ {
        for charSet[s[r]] {
            delete(charSet, s[l])
            l++
        }
        charSet[s[r]] = true
        if r - l + 1 > res {
            res = r - l + 1
        }
    }
    return res
}

class Solution {
    fun lengthOfLongestSubstring(s: String): Int {
        val charSet = HashSet<Char>()
        var l = 0
        var res = 0

        for (r in s.indices) {
            while (s[r] in charSet) {
                charSet.remove(s[l])
                l++
            }
            charSet.add(s[r])
            res = maxOf(res, r - l + 1)
        }
        return res
    }
}

class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var charSet = Set<Character>()
        var l = 0, res = 0
        let chars = Array(s)

        for r in 0..<chars.count {
            while charSet.contains(chars[r]) {
                charSet.remove(chars[l])
                l += 1
            }
            charSet.insert(chars[r])
            res = max(res, r - l + 1)
        }
        return res
    }
}

impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        let s = s.as_bytes();
        let mut char_set = HashSet::new();
        let mut l = 0;
        let mut res = 0;

        for r in 0..s.len() {
            while char_set.contains(&s[r]) {
                char_set.remove(&s[l]);
                l += 1;
            }
            char_set.insert(s[r]);
            res = res.max(r - l + 1);
        }
        res as i32
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(m)$

Where $n$ is the length of the string and $m$ is the total number of unique characters in the string.

3. Sliding Window (Optimal)

Intuition

Instead of removing characters one by one when we see a repeat, we can jump the left pointer directly to the correct position.
We keep a map that stores the last index where each character appeared.
When a character repeats, the earliest valid starting point moves to one position after its previous occurrence.
This lets us adjust the window in one step and always keep it valid, making the approach fast and clean.

Algorithm

Create a map mp to store the last index of each character.
Initialize:
- l = 0 for the start of the window,
- res = 0 for the longest length.
Loop through the string with index r:
- If s[r] is already in mp, move l to mp[s[r]] + 1, but never backward.
- Update mp[s[r]] = r.
- Update the longest length: res = max(res, r - l + 1).
Return res at the end.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        mp = {}
        l = 0
        res = 0

        for r in range(len(s)):
            if s[r] in mp:
                l = max(mp[s[r]] + 1, l)
            mp[s[r]] = r
            res = max(res, r - l + 1)
        return res

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> mp = new HashMap<>();
        int l = 0, res = 0;

        for (int r = 0; r < s.length(); r++) {
            if (mp.containsKey(s.charAt(r))) {
                l = Math.max(mp.get(s.charAt(r)) + 1, l);
            }
            mp.put(s.charAt(r), r);
            res = Math.max(res, r - l + 1);
        }
        return res;
    }
}

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> mp;
        int l = 0, res = 0;

        for (int r = 0; r < s.size(); r++) {
            if (mp.find(s[r]) != mp.end()) {
                l = max(mp[s[r]] + 1, l);
            }
            mp[s[r]] = r;
            res = max(res, r - l + 1);
        }
        return res;
    }
};

class Solution {
    /**
     * @param {string} s
     * @return {number}
     */
    lengthOfLongestSubstring(s) {
        let mp = new Map();
        let l = 0,
            res = 0;

        for (let r = 0; r < s.length; r++) {
            if (mp.has(s[r])) {
                l = Math.max(mp.get(s[r]) + 1, l);
            }
            mp.set(s[r], r);
            res = Math.max(res, r - l + 1);
        }
        return res;
    }
}

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        Dictionary<char, int> mp = new Dictionary<char, int>();
        int l = 0, res = 0;

        for (int r = 0; r < s.Length; r++) {
            if (mp.ContainsKey(s[r])) {
                l = Math.Max(mp[s[r]] + 1, l);
            }
            mp[s[r]] = r;
            res = Math.Max(res, r - l + 1);
        }
        return res;
    }
}

func lengthOfLongestSubstring(s string) int {
    mp := make(map[byte]int)
    l, res := 0, 0

    for r := 0; r < len(s); r++ {
        if idx, found := mp[s[r]]; found {
            l = max(idx+1, l)
        }
        mp[s[r]] = r
        if r - l + 1 > res {
            res = r - l + 1
        }
    }
    return res
}

class Solution {
    fun lengthOfLongestSubstring(s: String): Int {
        val mp = HashMap<Char, Int>()
        var l = 0
        var res = 0

        for (r in s.indices) {
            if (s[r] in mp) {
                l = maxOf(mp[s[r]]!! + 1, l)
            }
            mp[s[r]] = r
            res = maxOf(res, r - l + 1)
        }
        return res
    }
}

class Solution {
    func lengthOfLongestSubstring(_ s: String) -> Int {
        var mp = [Character: Int]()
        var l = 0, res = 0
        let chars = Array(s)

        for r in 0..<chars.count {
            if let index = mp[chars[r]] {
                l = max(index + 1, l)
            }
            mp[chars[r]] = r
            res = max(res, r - l + 1)
        }
        return res
    }
}

impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        let s = s.as_bytes();
        let mut mp = HashMap::new();
        let mut l = 0usize;
        let mut res = 0;

        for r in 0..s.len() {
            if let Some(&idx) = mp.get(&s[r]) {
                l = l.max(idx + 1);
            }
            mp.insert(s[r], r);
            res = res.max(r - l + 1);
        }
        res as i32
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(m)$

Where $n$ is the length of the string and $m$ is the total number of unique characters in the string.

Common Pitfalls

Not Taking the Maximum When Jumping the Left Pointer

In the optimal sliding window approach, when you find a duplicate character, you should move the left pointer to max(left, lastIndex[char] + 1). Forgetting the max operation can cause the left pointer to move backwards if the duplicate character's last occurrence is before the current window start, leading to incorrect results.

Forgetting to Update the Character's Last Index

After processing each character, you must update its last seen index in the map, regardless of whether it was a duplicate. Failing to update the index means future duplicate checks will reference stale positions, causing incorrect window calculations.

Off-by-One in Window Size Calculation

When calculating the substring length, ensure you use right - left + 1 since both indices are inclusive. Using right - left will undercount the length by one, resulting in an answer that is consistently one less than correct.