Longest Substring Without Repeating Characters – 3. LeetCode

Imagine you’re reading a sentence and trying to find the longest stretch of letters where no letter is repeated. The goal is to figure out the maximum length of such a stretch of unique characters without having to go through every possible combination.

Brute Force Approach

class Solution {
    public int LengthOfLongestSubstring(string s) {
        int maxLength = 0;

        for (int i = 0; i < s.Length; i++) {
            HashSet<char> charSet = new HashSet<char>();
            for (int j = i; j < s.Length; j++) {
                if (charSet.Contains(s[j])) break;
                charSet.Add(s[j]);
                maxLength = Math.Max(maxLength, j - i + 1);
            }
        }

        return maxLength;
    }
}

• Start from every character in the string
• Expand the substring by adding characters until a duplicate is found.
• Track the max length of all such substrings.

Optimal Approach

Algorithm & Data Structure

• Algorithm: Sliding Window

• Data Structure: HashSet

Intuition:

Instead of repeatedly restarting from each character like in brute force, maintain a “window” of unique characters. As you slide the window through the string:

• Expand the window by adding new characters (moving the right pointer).

• Shrink the window by removing old characters (moving the left pointer) if duplicates are found.

This approach ensures that every character is processed only once, making it much faster.

Steps of Algorithm:

1. Initialize two pointers (left and right) and a HashSet to track unique characters.

2. Expand the window by moving the right pointer and adding characters to the HashSet.

3. If a duplicate is found, shrink the window by moving the left pointer and removing characters.

4. Continuously update the maximum length.

5. Return the maximum length at the end.

import java.util.HashSet;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0; // Left pointer for the sliding window
        int right = 0; // Right pointer for the sliding window
        int maxLength = 0; // Variable to track the maximum length
        HashSet<Character> charSet = new HashSet<>(); // Set to store unique characters

        // Iterate through the string
        while (right < s.length()) {
            if (!charSet.contains(s.charAt(right))) {
                charSet.add(s.charAt(right)); // Add character to the set
                right++; // Expand the window
                maxLength = Math.max(maxLength, right - left); // Update max length
            } else {
                charSet.remove(s.charAt(left)); // Remove the leftmost character
                left++; // Shrink the window
            }
        }
        return maxLength; // Return the maximum length
    }
}

Line By Line Description

Step 1: Initialize Variables

int left = 0;
int right = 0;
int maxLength = 0;
HashSet<Character> charSet = new HashSet<>();

• left and right: Start at the beginning of the array.
• maxLength: Records the longest substring of unique items found so far.
• charSet: Tracks what elements have been seen.

Step 2: Iterate

while (right < s.length()) {

• right pointer represents the current item in iteration

Step 3: Check For Duplicates

if (!charSet.contains(s.charAt(right))) {
    charSet.add(s.charAt(right));
    right++;
    maxLength = Math.max(maxLength, right - left);
} else {
    charSet.remove(s.charAt(left));
    left++;
}

• If the item is unique (already in set):
  • Add it to the charSet
  • Move right pointer to expand the window
  • Update maxLength if the session’s length (right-left) exceeds the previous max
• If the item is a duplicate:
  • Remove the leftmost item (left pointer)
  • Shrink the window until there are no duplicates
• To ensure window contains only unique items and adjust dynamically

Why This Code Works

This algorithm works efficiently because it uses the sliding window technique to dynamically adjust the range of characters being considered, ensuring each character is processed only once. By leveraging a HashSet to track unique characters, it avoids unnecessary recalculations and guarantees optimal time complexity of O(n). Its clear structure and adaptability to varying input lengths make it the best choice for solving the problem of finding the longest substring without repeating characters.