Longest Substring and Subarray Pattern Problems

Longest substring and subarray pattern problems represent fundamental algorithmic challenges that test your ability to optimize search spaces using sliding window techniques and two-pointer approaches. These problems frequently appear in FAANG interviews as they assess both algorithmic thinking and implementation skills.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. What is the expected size of the input array/string? Are we dealing with small inputs (≤ 1000) or large-scale data?
2. Can the input contain duplicate characters/elements, and should we treat them as valid in our substring/subarray?
3. Should we return the actual substring/subarray or just its length?
4. Are we allowed to mutate the input array/string during processing?
5. What is the target time complexity for follow-ups? O(n) or O(n log n) acceptable?

Restate the pattern or problem type in your own words: This pattern involves finding the longest contiguous sequence (substring or subarray) that satisfies specific criteria. It's a classic sliding window problem where we maintain a valid window and expand/contract it to find optimal solutions.

Clarify the signal words and constraint shape that point to it:

• "Longest", "maximum", "largest" — indicates we want an optimal length
• "Contiguous", "substring", "subarray" — tells us we're looking at continuous sequences
• "At most K", "at least K", "unique elements", "sum constraints" — these are common conditions that make sliding window optimal
• "Dynamic window size" — suggests we need to adjust our window dynamically

Note any assumptions you are making:

• The problem likely involves a single pass through the data with window expansion/contraction
• We're looking for optimal contiguous sequences, not disjoint segments
• The constraints are typically simple enough to maintain in O(1) time per operation

Identify whether the pattern is best suited for static, streaming, or online scenarios: This pattern works best for static input scenarios where we have all data upfront. While the sliding window technique can be adapted for streaming, the standard implementation assumes we know all elements in advance. The pattern is most commonly used in competitive programming and coding interviews for static datasets where we want to find optimal contiguous subsequences under specific constraints.

The key insight is that for many such problems, we can maintain a valid window and expand it greedily while ensuring the constraint is satisfied, making it an efficient O(n) solution when properly implemented.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "Longest substring," "longest subarray," "maximum length," "largest window"
• "At most k distinct characters," "at least one repeated element," "no duplicates allowed"
• "Sliding window" or "two pointers" terminology
• Constraints like "substring with at most k distinct elements" or "subarray with sum at most target"
• Problems asking for maximum or minimum length satisfying a condition

Why this pattern fits better than the most common alternatives: This pattern is ideal when we need to find optimal contiguous substructures (strings or arrays) under constraints that can be efficiently maintained with a sliding window approach. Unlike brute-force O(n³) solutions checking all substrings or subarrays, sliding window techniques can achieve O(n) time complexity by maintaining a valid window and expanding/contracting it intelligently.

Conditions where a variation or related pattern applies instead:

• If the problem requires tracking multiple independent windows or disjoint subarrays, a greedy approach might be better
• For problems requiring all valid substrings rather than just the longest one, backtracking or dynamic programming could apply
• When elements are not contiguous (e.g., subsequence problems), we'd use dynamic programming instead of sliding window
• If the constraint is not monotonic (e.g., "substring with exactly k distinct characters" where k changes dynamically), we might need to use hash maps with more complex tracking

The core insight that makes this pattern work: The key insight is that for many constraint-based optimization problems, if we fix one end of a valid window, the other end can only move in one direction (either expanding or contracting). This monotonicity allows us to use two pointers to efficiently explore all valid windows without redundant checks, reducing the search space from O(n²) to O(n).

3. Approach Evolution

Interview communication script:

My first instinct is to use a brute force approach where I check every possible substring to find the longest one with unique characters. But that's O(n³) because for each starting position I'd need to check all ending positions, and then validate uniqueness for each substring. That's too slow.

Let me think about how to optimize this. I notice that if I maintain a sliding window with two pointers, I can avoid redundant checks. If I expand the right pointer and find a duplicate character, instead of restarting from scratch, I can shrink the window from the left until that duplicate is removed.

I notice that if I maintain a sliding window invariant where all characters in the current window are unique, I can reduce it to O(n) time by using a hash map to track character positions. When I encounter a duplicate, I can jump the left pointer directly to the position after the previous occurrence.

Let me think about this more carefully. The key insight is that once I find a duplicate character, I don't need to shrink the window one by one - I can jump directly to the position right after the previous occurrence of that character. This maintains linear time complexity.

Brute-force approach and why it is not ideal:

The brute force approach would check all possible substrings by:

1. For each starting position i, check all ending positions j ≥ i
2. For each substring s[i:j+1], verify that all characters are unique
3. Track the maximum length found

This approach has O(n³) time complexity because:

• O(n²) substrings to check
• O(n) time to validate uniqueness for each substring
• Space complexity is O(1) if we don't store intermediate results

This is inefficient because it recomputes the same character uniqueness checks multiple times.

Improved approach and the key optimization:

The key optimization is to use a sliding window technique with two pointers (left and right) that maintain a valid window where all characters are unique. The key insight is:

1. Expand the right pointer to include new characters
2. When we encounter a duplicate character, instead of shrinking one by one, we jump the left pointer to just after the previous occurrence of that character
3. This ensures each character is processed at most twice (once when added, once when removed)

Final approach with step-by-step reasoning:

1. Use two pointers (left and right) to maintain a sliding window
2. Use a HashMap to store the most recent index of each character
3. For each new character at position right:
   • If the character exists in current window (its last occurrence index ≥ left), move left pointer to max(left, previous_index + 1)
   • Update the character's most recent index in the map
   • Calculate window size and update maximum length if needed
4. Continue until right pointer reaches end of string

Important invariants that must hold:

1. The window [left, right] always contains only unique characters
2. For any character in the current window, its last occurrence index is ≥ left
3. The map stores the most recent index of each character in current window
4. Left pointer never moves backward (ensures linear time complexity)
5. Window size is always valid (no duplicate characters in current window)

4. Data Structure Choice

For the longest substring/subarray pattern, the primary data structure is a sliding window approach with two pointers. The key data structures needed are:

1. Two integer pointers (left and right) - to maintain the current window bounds
2. HashMap or HashSet - to track character/element frequencies or presence in current window
3. Integer variables - to store maximum length found so far

Why Each Data Structure Is Needed:

The sliding window technique with two pointers is essential because it allows us to maintain a valid substring/subarray while efficiently expanding and contracting the window. The left pointer represents the start of our current valid window, and the right pointer expands it.

The HashMap/HashSet is crucial for tracking character frequencies or element uniqueness within the current window. For problems like "Longest Substring Without Repeating Characters", we need to quickly check if a character has been seen in the current window. A HashMap allows us to store character frequencies, while a HashSet works when we only care about presence.

The integer variables are needed to track the maximum length found so far and update it as we expand valid windows.

Time and Space Impact:

• Time Complexity: O(n) for the sliding window approach where n is the input size
• Space Complexity: O(min(m,n)) where m is the size of the character set and n is input length
  • For unique character problems, this becomes O(min(k,n)) where k is the size of the character set (e.g., 26 for lowercase letters)
  • In worst case with all unique characters, it's O(n)

Helper Structures:

A HashMap is used as a helper to maintain character frequencies, enabling O(1) lookup and update operations. This is more efficient than maintaining a separate array for character tracking, especially when dealing with extended ASCII or Unicode characters.

The sliding window approach naturally handles the expansion and contraction of the valid substring through pointer management, making it a clean and efficient solution without requiring complex data structure manipulation.

5. Algorithm Walkthrough

Let's trace through the algorithm using the example s = "abcabcbb" with window sliding approach:

Step 1: Initialize left = 0, maxLength = 0, and charIndexMap as empty.

Step 2: Process s[0] = 'a':

• Character 'a' not in map, so add it: charIndexMap['a'] = 0
• Current window size = 0 - 0 + 1 = 1
• Update maxLength = max(0, 1) = 1

Step 3: Process s[1] = 'b':

• Character 'b' not in map, so add it: charIndexMap['b'] = 1
• Current window size = 1 - 0 + 1 = 2
• Update maxLength = max(1, 2) = 2

Step 4: Process s[2] = 'c':

• Character 'c' not in map, so add it: charIndexMap['c'] = 2
• Current window size = 2 - 0 + 1 = 3
• Update maxLength = max(2, 3) = 3

Step 5: Process s[3] = 'a':

• Character 'a' exists in map at index 0
• Since 0 >= left, we must move left pointer: left = 0 + 1 = 1
• Update index of 'a': charIndexMap['a'] = 3
• Current window size = 3 - 1 + 1 = 3
• maxLength remains 3

Step 6: Process s[4] = 'b':

• Character 'b' exists in map at index 1
• Since 1 >= left, we must move left pointer: left = 1 + 1 = 2
• Update index of 'b': charIndexMap['b'] = 4
• Current window size = 4 - 2 + 1 = 3
• maxLength remains 3

Step 7: Process s[5] = 'c':

• Character 'c' exists in map at index 2
• Since 2 >= left, we must move left pointer: left = 2 + 1 = 3
• Update index of 'c': charIndexMap['c'] = 5
• Current window size = 5 - 3 + 1 = 3
• maxLength remains 3

Step 8: Process s[6] = 'b':

• Character 'b' exists in map at index 4
• Since 4 >= left, we must move left pointer: left = 4 + 1 = 5
• Update index of 'b': charIndexMap['b'] = 6
• Current window size = 6 - 5 + 1 = 2
• maxLength remains 3

Step 9: Process s[7] = 'b':

• Character 'b' exists in map at index 6
• Since 6 >= left, we must move left pointer: left = 6 + 1 = 7
• Update index of 'b': charIndexMap['b'] = 7
• Current window size = 7 - 7 + 1 = 1
• maxLength remains 3

Step 10: Process s[8] = 'b':

• Character 'b' exists in map at index 7
• Since 7 >= left, we must move left pointer: left = 7 + 1 = 8
• Update index of 'b': charIndexMap['b'] = 8
• Current window size = 8 - 8 + 1 = 1
• maxLength remains 3

Final result: maxLength = 3 for substring "abc".

The algorithm correctly handles:

• Expanding window when no duplicates found
• Contracting window when duplicate found within current window
• Maintaining maximum length throughout the process
• Properly updating character indices to reflect latest positions

The key invariant maintained is that left always points to the start of a valid substring with no repeated characters, and charIndexMap stores the most recent index for each character.

6. Java Solution

public class LongestSubstringWithoutRepeating {
    
    /**
     * Finds the length of the longest substring without repeating characters
     * Uses sliding window technique with HashMap to track character positions
     * 
     * @param s input string
     * @return length of longest substring without repeating characters
     */
    public int lengthOfLongestSubstring(String s) {
        // Handle edge case of empty string
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        // Map to store the most recent index of each character
        Map<Character, Integer> charIndexMap = new HashMap<>();
        
        int maxLength = 0;
        int left = 0; // Left pointer of sliding window
        
        // Iterate through string with right pointer
        for (int right = 0; right < s.length(); right++) {
            char currentChar = s.charAt(right);
            
            // If character was seen and is within current window
            if (charIndexMap.containsKey(currentChar) && 
                charIndexMap.get(currentChar) >= left) {
                // Move left pointer to one position after the last occurrence
                left = charIndexMap.get(currentChar) + 1;
            }
            
            // Update the most recent index of current character
            charIndexMap.put(currentChar, right);
            
            // Update maximum length if current window is larger
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
    
    /**
     * Alternative implementation using HashSet for character tracking
     * This approach is more intuitive but requires inner loop in worst case
     */
    public int lengthOfLongestSubstringHashSet(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        Set<Character> charSet = new HashSet<>();
        int maxLength = 0;
        int left = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char currentChar = s.charAt(right);
            
            // Shrink window until no duplicate
            while (charSet.contains(currentChar)) {
                char leftChar = s.charAt(left);
                charSet.remove(leftChar);
                left++;
            }
            
            charSet.add(currentChar);
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

This solution implements the sliding window technique with a HashMap to achieve O(n) time complexity. The key insight is maintaining a map of character positions to efficiently move the left pointer when duplicates are found, avoiding the need for nested loops. The HashSet alternative is provided for comparison but has worse worst-case time complexity.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm uses a sliding window approach with two pointers that traverse the input array exactly once. Each element is visited at most twice (once by the right pointer, once by the left pointer), resulting in linear time complexity. The inner while loop that adjusts the window is amortized O(1) because each element is added and removed from the HashSet at most once across the entire execution.

Space Complexity: O(min(m,n))

Where m is the size of the character set (e.g., 26 for lowercase letters, 128 for ASCII) and n is the length of the input string. The HashSet stores at most min(m,n) characters in the current window, as it cannot contain more distinct characters than either the available character set or the string length. In the worst case with all unique characters, it will store up to n characters.

Why These Bounds Are Correct

The time bound is tight because we process each element exactly once in the outer loop, and the inner loop's work is amortized across all iterations. The space bound is tight because the HashSet size is bounded by the smaller of the character set size or string length, and we never store duplicate characters in the window.

Optimality

This solution is optimal for the problem as stated. We must examine each character at least once to determine the longest substring, making O(n) time complexity unavoidable. The space usage is also optimal for maintaining the necessary state to track character uniqueness within a sliding window.

The solution achieves the best possible complexity trade-off for this constraint satisfaction problem, balancing between time efficiency and space usage.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty string/array: Returns 0 for length, handles gracefully with initial bounds check
• Single character: Correctly returns 1 without any sliding window operations
• Two identical characters: Properly identifies the longest valid substring

Duplicate Values and Repeated States

• All duplicates: Algorithm correctly handles cases like "aaaa" where the sliding window shrinks appropriately
• Duplicate characters in valid range: When a duplicate is found, the left pointer advances to maintain uniqueness constraint
• Character frequency tracking: Must ensure that character counts are properly maintained in the hash map

Boundary Conditions

• String with only one unique character: Algorithm correctly identifies this as valid substring of length 1
• Very large input size: The solution handles inputs up to the constraint limits (e.g., 5 * 10^4 characters)
• Character set boundaries: The solution works with any valid ASCII character, not just lowercase letters

Common Implementation Mistakes

• Incorrect window expansion: Forgetting to update the character frequency map when expanding the right pointer
• Wrong shrinkage condition: Not properly checking if a character count exceeds 1 before shrinking the window
• Off-by-one errors: Mismanaging the indices when updating left pointer or returning final result
• Not resetting character counts: Failing to decrement character counts when moving the left pointer, leading to incorrect state
• Missing bounds checks: Not handling edge cases like null input or empty collections before processing

Key Implementation Considerations

The most critical pitfall is maintaining the invariant that the current window contains at most one duplicate character. This requires careful tracking of character frequencies and proper updating of the sliding window bounds during both expansion and contraction phases.

9. Alternative Approaches

There are several alternative approaches to solving longest substring/subarray problems, each with different trade-offs:

Brute Force Approach: Check all possible substrings using nested loops. Time complexity O(n³) - O(n²) for generating substrings and O(n) for validation. This approach is simple to implement but inefficient for large inputs.

Hash Map with Sliding Window: Similar to our optimal solution but using a HashMap to track character frequencies instead of a fixed-size array. This works well for problems where we need to track multiple character occurrences, but requires more space and has slightly higher constant factors.

Two Pointers with Frequency Array: Using a fixed-size array (e.g., 256 elements for ASCII) to track character occurrences instead of a HashMap. This is more memory-efficient than HashMap but only works when we know the character set size in advance.

Dynamic Programming: Maintain a DP table where dp[i][j] represents whether substring from i to j satisfies the constraint. This approach has O(n²) time complexity and is more complex to implement, but can be useful when we need to track multiple constraints or when the problem structure naturally fits a DP formulation.

Set-based Sliding Window: Using a HashSet to track unique characters in the current window. This approach works well for problems requiring unique elements but requires additional space and is less efficient than our fixed-size array approach.

The chosen solution using fixed-size array with sliding window is optimal for the specific constraint of English letters, offering O(n) time and O(1) space complexity with clean implementation and minimal overhead.

10. Test Cases

public class TestCases {
    public static void main(String[] args) {
        // Test case 1: Basic example
        // Input: "abcabcbb" -> Output: 3 ("abc")
        System.out.println("Test 1: " + lengthOfLongestSubstring("abcabcbb"));
        
        // Test case 2: All unique characters
        // Input: "abcdef" -> Output: 6 ("abcdef")
        System.out.println("Test 2: " + lengthOfLongestSubstring("abcdef"));
        
        // Test case 3: Empty string
        // Input: "" -> Output: 0
        System.out.println("Test 3: " + lengthOfLongestSubstring(""));
        
        // Test case 4: Single character
        // Input: "a" -> Output: 1
        System.out.println("Test 4: " + lengthOfLongestSubstring("a"));
        
        // Test case 5: All same characters
        // Input: "aaaa" -> Output: 1
        System.out.println("Test 5: " + lengthOfLongestSubstring("aaaa"));
        
        // Test case 6: Complex overlapping
        // Input: "pwwkew" -> Output: 3 ("wke")
        System.out.println("Test 6: " + lengthOfLongestSubstring("pwwkew"));
        
        // Test case 7: With spaces and special characters
        // Input: "ab ba" -> Output: 3 ("ab ")
        System.out.println("Test 7: " + lengthOfLongestSubstring("ab ba"));
        
        // Test case 8: Large input with no duplicates
        // Input: "abcdefghijklmnopqrstuvwxyz" -> Output: 26
        String longStr = "abcdefghijklmnopqrstuvwxyz";
        System.out.println("Test 8: " + lengthOfLongestSubstring(longStr));
    }
}

Sample Test Cases:

1. Basic example: "abcabcbb" → Expected: 3 (substring "abc")
2. All unique characters: "abcdef" → Expected: 6 (entire string)
3. Empty input: "" → Expected: 0
4. Single character: "a" → Expected: 1
5. Repeated characters: "aaaa" → Expected: 1 (no repeating chars allowed)
6. Complex overlapping: "pwwkew" → Expected: 3 (substring "wke")
7. With spaces: "ab ba" → Expected: 3 (substring "ab ")
8. Large unique input: "abcdefghijklmnopqrstuvwxyz" → Expected: 26

Tricky Case:

• Input: "dvdf" → Expected: 3 (substring "vdf") - requires careful handling of duplicate character at index 2

Boundary Case:

• Input: "" (empty string) → Expected: 0 - edge case for empty input handling

11. Final Summary

The core idea is to use the sliding window technique with a hashmap to track character frequencies, enabling us to efficiently find the longest substring with at most k distinct characters in linear time. This solution works by maintaining a valid window that expands when we can include more characters and contracts when we exceed the k distinct character limit, ensuring optimal performance with O(n) time complexity. The key insight is that we only need to track the rightmost occurrence of each character to properly adjust our window bounds, making this approach both elegant and efficient for the given constraint.