Techie Hub

3. Longest Substring Without Repeating Characters - Leetcode

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

Featured Posts

3. Longest Substring Without Repeating Characters - Leetcode

Longest Substring Without Repeating Characters Difficulty: Medium Problem Statement: Given a string s , find the length of the longest ...

Popular Posts