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:
- Use two pointers:
left
(start of the substring)right
(expanding end of the substring)
- Maintain a HashSet to track unique characters in the current window.
- Expand the window by moving
right
until a duplicate character is found. - If a duplicate is found, move
left
forward until the duplicate is removed. - 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.