31. Longest Substring Without Repeating Characters

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

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Input: s = "bbbbb"
Output: 1

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.

Problem Breakdown:

1. Use a sliding window with a set to track characters in the current window. Maintain left and right pointers.

• charSet = set()
  left = 0
  maxLen = 0

2. Expand the window by moving right. If the character is already in the set, shrink from the left until it is removed.

• for right in range(len(s)):
      while s[right] in charSet:
          charSet.remove(s[left])
          left += 1

3. Add the current character to the set and update the maximum length.

•     charSet.add(s[right])
      maxLen = max(maxLen, right - left + 1)

4. After processing all characters, return the maximum length found.

• return maxLen

Summary:

Sliding window with a hash set. Expand the right boundary and add characters. When a duplicate is found, shrink from the left until the duplicate is removed. Track the maximum window size throughout.

Time and Space Complexity:

Time Complexity: O(n) - each character is visited at most twice (once by right, once by left).

Space Complexity: O(min(n, m)) - where m is the size of the character set.

Python Solution:

def lengthOfLongestSubstring(s):
    charSet = set()
    left = 0
    maxLen = 0
    for right in range(len(s)):
        while s[right] in charSet:
            charSet.remove(s[left])
            left += 1
        charSet.add(s[right])
        maxLen = max(maxLen, right - left + 1)
    return maxLen

JavaScript Solution:

var lengthOfLongestSubstring = function(s) {
    const charSet = new Set();
    let left = 0, maxLen = 0;
    for (let right = 0; right < s.length; right++) {
        while (charSet.has(s[right])) {
            charSet.delete(s[left]);
            left++;
        }
        charSet.add(s[right]);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
};

Java Solution:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set charSet = new HashSet<>();
        int left = 0, maxLen = 0;
        for (int right = 0; right < s.length(); right++) {
            while (charSet.contains(s.charAt(right))) {
                charSet.remove(s.charAt(left));
                left++;
            }
            charSet.add(s.charAt(right));
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}