Leetcode Problem 3 - Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters

Difficulty: Medium

Problem Statement:
Given a string s, find the length of the longest substring without repeating characters.

---

Example 1:

Input:

s = "abcabcbb"

Output:

3

Explanation:

The longest substring without repeating characters is "abc", with a length of 3.

---

Example 2:

Input:

s = "bbbbb"

Output:

1

Explanation:

The longest substring without repeating characters is "b", with a length of 1.

---

Example 3:

Input:

s = "pwwkew"

Output:

3

Explanation:

The longest substring without repeating characters is "wke", with a length of 3.
Note: The answer must be a substring (continuous), not a subsequence.

---

Constraints

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

---

Solution Approach: Sliding Window + HashSet

We use the Sliding Window technique with a HashSet to efficiently track characters in the current substring.

Algorithm:

1. Use two pointers:
   • left (start of the substring)
   • right (expanding end of the substring)
2. Maintain a HashSet to track unique characters in the current window.
3. Expand the window by moving right until a duplicate character is found.
4. If a duplicate is found, move left forward until the duplicate is removed.
5. Keep track of the maximum window size encountered.

---

Code Implementation (C#)

using System;
using System.Collections.Generic;

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        HashSet<char> set = new HashSet<char>();
        int left = 0, maxLength = 0;

        for (int right = 0; right < s.Length; right++) {
            while (set.Contains(s[right])) {
                set.Remove(s[left]);
                left++;
            }

            set.Add(s[right]);
            maxLength = Math.Max(maxLength, right - left + 1);
        }

        return maxLength;
    }
}

// Example Usage
class Program {
    static void Main() {
        Solution solution = new Solution();

        Console.WriteLine(solution.LengthOfLongestSubstring("abcabcbb")); // Output: 3
        Console.WriteLine(solution.LengthOfLongestSubstring("bbbbb"));    // Output: 1
        Console.WriteLine(solution.LengthOfLongestSubstring("pwwkew"));   // Output: 3
    }
}

---

Why This Approach?

✅ Efficient (O(n) instead of O(n²))
✅ Handles all edge cases (empty string, all unique, all same characters, etc.)
✅ Easy to understand and implement

This is an optimal solution for Longest Substring Without Repeating Characters.