Longest Substring Without Repeating Characters

LeetCode 3 | Difficulty: Medium

Medium

Problem Description

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

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3. Note that "bca" and "cab" are also correct answers.

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.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

- `0 <= s.length <= 5 * 10^4`

- `s` consists of English letters, digits, symbols and spaces.

Topics: Hash Table, String, Sliding Window

---

Approach

Sliding Window

Maintain a window [left, right] over the array/string. Expand right to include new elements, and shrink left when the window violates constraints. Track the optimal answer as the window slides.

When to use

Finding subarrays/substrings with a property (max length, min length, exact count).

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

---

Solutions

Solution 1: C# (Best: 84 ms)

Metric	Value
Runtime	84 ms
Memory	39.5 MB
Date	2021-11-29

Solution

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        int n = s.Length;
    Dictionary<char, int> seen = new Dictionary<char, int>();
    int max = 0, j =0   ;
    
    for (int i = 0; i < n; i++)
    {
        if(seen.ContainsKey(s[i]))
        {
            j = Math.Max(j, seen[s[i]]+1);
            seen[s[i]] = i;
        }
        else 
        seen.Add(s[i],i);
        max = Math.Max(max, i - j + 1);
    }
    
    return max;
    }
}

📜 2 more C# submission(s)

Submission (2020-03-13) — 100 ms, 25 MB

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        if(string.IsNullOrEmpty(s)) return 0;
    if(s.Length==1) return 1;
    
    int len = s.Length;
    int i=0, j=1;
    List<char> wc = new List<char>();
    wc.Add(s[0]);
    int maxLen = 0;
    while(j<len)
    {
        if(!wc.Contains(s[j]))
        {
            wc.Add(s[j]);
            j++;
            
        }
        else
        {
            maxLen = Math.Max(maxLen, j-i);
            
            //reduce current sliding window
            while(s[i]!=s[j])
            {
                wc.Remove(s[i]);
                i++;                
            }
            wc.Remove(s[i]);
            i++;
        }
    }
    maxLen = Math.Max(maxLen, j-i);
    return maxLen;
}
}

Submission (2017-07-13) — 138 ms, N/A

using System;

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        if(string.IsNullOrEmpty(s)) return 0;
        Dictionary<char, int> map = new Dictionary<char, int>();
        int max = 0;
        for(int i=0, j=0; i<s.Length;i++)
        {
            if(map.ContainsKey(s[i]))
            {
                j = Math.Max(j, map[s[i]]+1);
            }
            map[s[i]] = i;
            max = Math.Max(max, i-j+1);
        }
        
        return max;
        
    }
}

---

Complexity Analysis

Approach	Time	Space
Sliding Window	$O(n)$	$O(k)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Clarify what makes a window "valid" and what triggers expansion vs shrinking.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 1 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Generate all possible substrings & check for each substring if it's valid and keep updating maxLen accordingly.