L3. Longest Substring Without Repeating Characters | 2 Pointers and Sliding Window Playlist

This chapter explores how to solve the classic Longest Substring Without Repeating Characters problem. We will journey from a naive $O(N^2)$ brute-force approach using nested loops and hashing to an optimized $O(N)$ solution utilizing a sliding window pattern with two pointers and a character frequency/index tracking array.

1. Problem Statement & Definition

You are given a string $s$ containing any combination of characters from the 256 possible ASCII characters (lowercase, uppercase, special characters, digits). Your goal is to find the length of the longest substring that contains no repeating characters.

Core Definitions:

• Substring: A contiguous sequence of characters within a string. For example, in "cadbz", "cad" is a valid substring, whereas "ca" and "c" is valid, but "cac" or "ca...z" (discontinuous) is not.
• Goal: Return the maximum length of such a substring, not the substring itself.

String: c a d b z a b c d
         |     |
         L     R  (Valid substring window: length 5)

2. Naive Brute Force Approach ($O(N^2)$)

To understand why optimization is needed, let's examine the brute-force strategy. We can systematically generate every possible contiguous substring starting from each index $i$ and expanding with a second pointer $j$.

Brute Force Algorithm Idea:

1. Initialize an outer pointer $i$ from index $0$ to $N-1$.
2. Initialize an inner pointer $j$ starting at $i$, extending to the right.
3. Maintain a hash structure (or frequency array) to check for character repetition.
4. The moment a character repeats within the current window, terminate the inner loop (since expanding further will only maintain or worsen the repetition).
5. Track the maximum length encountered.

Brute-Force Pseudo-Code:

max_length = 0
for i in range(n):
    # Hash array for 256 ASCII characters
    hash_array = [0] * 256 
    for j in range(i, n):
        char_code = ord(s[j])
        if hash_array[char_code] == 1:
            break # Repeating character found; stop expanding this window
        
        current_length = j - i + 1
        max_length = max(max_length, current_length)
        hash_array[char_code] = 1

return max_length

Complexity of Naive Approach:

• Time Complexity: $O(N^2)$ because we explore all possible starting points and expand across the string.
• Space Complexity: $O(256) \approx O(1)$ for the fixed-size ASCII hash array.

3. The Need for Optimization: Two Pointers & Sliding Window

An interviewer will typically reject the $O(N^2)$ brute-force solution for large strings. We need an approach that runs closer to linear time, i.e., $O(N)$.

Core Mental Model / Analogy

Real-Life Analogy: Imagine sliding a transparent viewing window across a ticker tape of letters. Your right hand (R) moves forward to pull new letters into the window. Your left hand (L) only moves forward when a duplicate letter appears inside your window, squeezing the window from the left until the duplicate is dropped out.

The sliding window pattern is not a rigid rigid algorithm; it is a constructive problem-solving template where the window expands and contracts dynamically based on constraints.

4. Step-by-Step Sliding Window Dry Run

Let's trace the optimized two-pointer approach on the string: "cadbza"

1. Initialization:

   • L = 0, R = 0, max_length = 0
   • Hash array of size 256 initialized to -1 (storing the last seen index of each character).

2. Expanding R:

   • R = 0 (char 'c'): Not in hash. Length = 0 - 0 + 1 = 1. Update max_length = 1. Mark hash of 'c' to index 0.
   • R = 1 (char 'a'): Not in hash. Length = 1 - 0 + 1 = 2. Update max_length = 2. Mark hash of 'a' to index 1.
   • R = 2 (char 'd'): Not in hash. Length = 3. Update max_length = 3. Mark hash of 'd' to index 2.
   • R = 3 (char 'b'): Not in hash. Length = 4. Update max_length = 4. Mark hash of 'b' to index 3.
   • R = 4 (char 'z'): Not in hash. Length = 5. Update max_length = 5. Mark hash of 'z' to index 4.

3. Encountering a Duplicate (R = 5, char 'a'):

   • We check hash for 'a'. It was previously seen at index 1.
   • Is this past occurrence inside our current active window [L, R]? Yes (1 >= L).
   • Therefore, we must jump our left pointer L to hash['a'] + 1, which is 1 + 1 = 2.
   • Window contracts: L moves from 0 to 2.
   • Update hash for 'a' to current index 5.

5. Optimized Algorithm Implementation

Here is the clean, production-ready logic for the optimized sliding window approach:

public class LongestSubstringWithoutRepeating {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if (n == 0) return 0;
        
        int maxLen = 0;
        int l = 0, r = 0;
        
        // Hash array to store the last seen index of each ASCII character
        int[] hash = new int[256];
        Arrays.fill(hash, -1);
        
        while (r < n) {
            char currentChar = s.charAt(r);
            int charCode = (int) currentChar;
            
            // Check if character exists in map and lies within the current window [l, r]
            if (hash[charCode] != -1 && hash[charCode] >= l) {
                l = hash[charCode] + 1;
            }
            
            // Calculate current window length
            int length = r - l + 1;
            maxLen = Math.max(maxLen, length);
            
            // Update the last seen index of the character and expand right pointer
            hash[charCode] = r;
            r++;
        }
        
        return maxLen;
    }
}

6. Edge Cases & Debugging Real-World Pitfalls

When implementing sliding window algorithms in production or coding interviews, pay close attention to these common pitfalls:

7. Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$
  • The right pointer r traverses the string from index $0$ to $N-1$ exactly once.
  • The left pointer l only moves forward and never backtracks. Across the entire execution, l and r traverse at most $2N$ steps.
• Space Complexity: $\mathcal{O}(256) \approx \mathcal{O}(1)$
  • The frequency hash array is fixed at size 256 regardless of the input string length $N$, consuming constant auxiliary space.

Summary and Key Takeaways

• Problem Definition: Finding the longest contiguous substring without repeating characters requires tracking uniqueness dynamically.
• Sub-Optimal vs Optimal: Brute-force generation of all substrings takes $\mathcal{O}(N^2)$, whereas the sliding window approach optimizes this to linear $\mathcal{O}(N)$ time.
• Two-Pointer Dynamics: The right pointer (r) expands the window continuously, while the left pointer (l) contracts the window conditionally when duplicates occur.
• Index-Based Hashing: Instead of storing boolean flags or clearing frequency maps, storing the exact last-seen index in an integer array allows l to jump instantly rather than step-by-step.
• Window Range Check: Always ensure that a character's stored historical index falls within the active window (>= l) before adjusting the left boundary.
• Constant Space: Utilizing a fixed-size array of 256 handles all standard ASCII characters in $\mathcal{O}(1)$ space complexity.