Longest Substring Without Repeating Characters

📋

Problem

Imagine you're typing a password and want to find the longest sequence of characters you've typed without repeating any letter, to ensure maximum complexity.

Given a string s, find the length of the longest substring without repeating characters. Input: A string s consisting of English letters, digits, symbols, and spaces. Output: An integer representing the length of the longest substring without any repeated characters.

1 ≤ length of s ≤ 10^5s consists of English letters, digits, symbols, and spaces

Edge cases: Empty string → 0String with all unique characters → length of entire stringString with all identical characters → 1

</>

IDE

def lengthOfLongestSubstring(s: str) -> int:public int lengthOfLongestSubstring(String s)int lengthOfLongestSubstring(string s)function lengthOfLongestSubstring(s)

def lengthOfLongestSubstring(s: str) -> int:
    # Write your solution here
    pass

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // Write your solution here
        return 0;
    }
}

#include <string>
using namespace std;

int lengthOfLongestSubstring(string s) {
    // Write your solution here
    return 0;
}

function lengthOfLongestSubstring(s) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 for non-empty strings due to missing base case or incorrect initialization.✅ Initialize max length to 0 and return 0 only if input string is empty.

Wrong: Length of entire string even if duplicates existNot shrinking window or not detecting duplicates properly.✅ Use a hash set or map to detect duplicates and move start pointer accordingly.

Wrong: Incorrect length due to off-by-one errorCalculating window length as right - left instead of right - left + 1.✅ Calculate window length as end index - start index + 1.

Wrong: Fails on duplicate characters by resetting window incorrectlyGreedy approach that resets window start to next character instead of jumping past last duplicate index.✅ Track last seen indices and update start pointer to max of current start and last duplicate index + 1.

Wrong: TLE on large inputUsing brute force or nested loops leading to O(n^2) or worse complexity.✅ Implement sliding window with hash map for O(n) time complexity.

✓

Test Cases

Focus on handling edge cases like empty strings and single characters.

Test tricky inputs with repeated characters and check window updates carefully.

Optimize your solution to linear time to handle large inputs efficiently.

t1_01basic

Input{"s":"abcabcbb"}

Expected3

⏱ Performance - must finish in 2000ms

The longest substring without repeating characters is 'abc' with length 3.

💡 Try using a sliding window to track characters without repeats.

💡 Use a hash set to check if a character is already in the current window.

💡 Expand the window by moving right pointer and shrink from left when duplicates appear.

Why it failed: Returned incorrect length; likely not shrinking window correctly when duplicates found. Fix by moving left pointer until duplicate removed.

✓ Correctly finds longest substring length using sliding window.

t1_02basic

Input{"s":"pwwkew"}

Expected3

⏱ Performance - must finish in 2000ms

The longest substring without repeating characters is 'wke' with length 3.

💡 Remember substrings must be contiguous and without repeats.

💡 Track characters and their indices to efficiently move the window.

💡 Update start pointer to index after previous occurrence of duplicate character.

Why it failed: Incorrect output due to not updating start pointer correctly on duplicate. Fix by storing last seen indices and updating start accordingly.

✓ Handles duplicates by updating window start correctly.

t2_01edge

Input{"s":""}

Expected0

⏱ Performance - must finish in 2000ms

Empty string has no substrings, so length is 0.

💡 Check how your code handles empty input.

💡 Make sure to return 0 if string length is zero.

💡 Add a base case for empty string before processing.

Why it failed: Fails on empty string by not returning 0 or causing error. Fix by adding base case: if s is empty, return 0 immediately.

✓ Correctly returns 0 for empty string.

t2_02edge

Input{"s":"a"}

Expected1

⏱ Performance - must finish in 2000ms

Single character string has longest substring length 1.

💡 Check behavior with single character input.

💡 Window should handle minimal length strings correctly.

💡 Ensure initialization of max length accounts for single character.

Why it failed: Fails single character input by returning 0 or error. Fix by initializing max length to at least 1 when string non-empty.

✓ Correctly handles single character input.

t2_03edge

Input{"s":"abcdef"}

Expected6

⏱ Performance - must finish in 2000ms

All characters unique, so longest substring is entire string length 6.

💡 Test with all unique characters to verify no premature window shrinking.

💡 Sliding window should expand to full length if no duplicates.

💡 Max length should update to full string length.

Why it failed: Incorrect output due to shrinking window unnecessarily. Fix by only shrinking when duplicates found.

✓ Correctly returns full length for all unique characters.

t3_01corner

Input{"s":"abba"}

Expected2

⏱ Performance - must finish in 2000ms

Longest substring without repeating characters is 'ab' or 'ba', length 2.

💡 Check how duplicates inside the window are handled.

💡 Use a hash map to store last seen indices to jump start pointer.

💡 Update start pointer to max of current start and last seen duplicate index + 1.

Why it failed: Fails by not updating start pointer correctly on duplicate 'b'. Fix by tracking last seen indices and moving start pointer forward properly.

✓ Correctly handles duplicate characters by updating window start.

t3_02corner

Input{"s":"dvdf"}

Expected3

⏱ Performance - must finish in 2000ms

Longest substring without repeating characters is 'vdf' with length 3.

💡 Beware of greedy approach that resets window on duplicate instead of moving start pointer.

💡 Use index tracking to jump start pointer past previous duplicate.

💡 Avoid restarting window from next character after duplicate; jump to last duplicate index + 1.

Why it failed: Fails greedy approach that resets window on duplicate 'd'. Fix by using last seen indices to jump start pointer forward.

✓ Handles non-trivial duplicates with index tracking.

t3_03corner

Input{"s":"tmmzuxt"}

Expected5

⏱ Performance - must finish in 2000ms

Longest substring without repeating characters is 'mzuxt' with length 5.

💡 Check off-by-one errors when updating max length.

💡 Ensure window length calculation is end - start + 1 or equivalent.

💡 Update max length after each window expansion or contraction.

Why it failed: Off-by-one error causes incorrect max length. Fix by correctly calculating window length as right - left + 1.

✓ Correctly calculates window length and max length.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this"}

Expectednull

⏱ Performance - must finish in 2000ms

Input length n=100000; solution must run in O(n) time to complete within 2 seconds.

💡 Brute force O(n^3) or O(n^2) will time out on large input.

💡 Use sliding window with hash map or hash set for O(n) solution.

💡 Avoid nested loops and repeated substring checks.

Why it failed: TLE due to O(n^2) or worse complexity. Fix by implementing O(n) sliding window with hash map.

✓ Solution runs in O(n) time and passes performance test.

Practice

1. You are given an integer array and a fixed window size k. The task is to find the contiguous subarray of length k that has the maximum average value. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Sliding window technique maintaining a running sum of the current window

B. Brute force nested loops checking all subarrays of size k

C. Dynamic programming with memoization of subproblems

D. Greedy approach selecting the largest elements regardless of position

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the maximum average of any contiguous subarray of fixed size k, which suggests examining all windows of size k.

2. Step 2: Identify optimal approach

   Sliding window maintains a running sum by adding the new element and removing the oldest, achieving O(n) time. Brute force is O(n*k), DP and greedy do not fit this fixed-size window problem optimally.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window updates sum in O(1) per step, total O(n) time [OK]

Hint: Sliding window updates sum in O(1) per step [OK]

Common Mistakes:

• Thinking greedy works without considering window contiguity
• Assuming DP is needed for fixed-size windows

2. Consider the following Python function implementing the sliding window approach to find the maximum sum subarray of size k. What is the value of window_sum after the second iteration of the for-loop when called with arr = [1, 3, 2, 6] and k = 2?

def max_sum_subarray_sliding_window(arr, k):
    n = len(arr)
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        if window_sum > max_sum:
            max_sum = window_sum
    return max_sum

easy

A. 8

B. 9

C. 5

D. 7

Solution

1. Step 1: Initialize variables

   window_sum = sum(arr[:2]) = 1 + 3 = 4, max_sum = 4

2. Step 2: Iterate and update window_sum

   First iteration (i=2): window_sum = 4 + arr[2] - arr[0] = 4 + 2 - 1 = 5 Second iteration (i=3): window_sum = 5 + arr[3] - arr[1] = 5 + 6 - 3 = 8

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   window_sum after second iteration is 8 [OK]

Hint: Track window_sum updates carefully per iteration [OK]

Common Mistakes:

• Off-by-one errors in loop index
• Confusing window_sum with max_sum
• Forgetting to subtract the element leaving the window

3. The following code attempts to find all anagrams of p in s using a sliding window with count matching optimization. Which line contains a subtle bug that can cause incorrect results or runtime errors?

medium

A. Line missing decrement of window_count[left_index] when shrinking window

B. Line checking if window_count[index] == p_count[index] + 1 to decrement matches

C. Line incrementing window_count[index] when adding right character

D. Line appending left index to result when matches == 26

Solution

1. Step 1: Identify window shrinking logic

   When window size exceeds p length, left character count must be decremented.

2. Step 2: Locate missing decrement

   The code does not decrement window_count[left_index] before moving left pointer, causing incorrect counts.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing decrement breaks frequency tracking [OK]

Hint: Always decrement count when shrinking window [OK]

Common Mistakes:

• Forgetting to decrement frequency on window shrink
• Incorrect matches update logic
• Appending wrong indices

4. What is the time complexity of the sliding window approach for the Minimum Size Subarray Sum problem, and why might some candidates incorrectly think it is O(n²)?

medium

A. O(n log n) due to sorting or binary search inside the loop

B. O(n²) because of nested loops implied by two pointers

C. O(n) because each element is visited at most twice by left and right pointers

D. O(n) but with O(n) auxiliary space for prefix sums

Solution

1. Step 1: Identify pointer movements

   Right pointer moves forward once per iteration; left pointer moves forward only when shrinking window, each element visited at most twice.

2. Step 2: Analyze total operations

   Since both pointers only move forward, total operations are proportional to 2n = O(n), no nested repeated scanning.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two-pointer sliding window is classic O(n) approach [OK]

Hint: Two pointers each move forward once -> O(n) [OK]

Common Mistakes:

• Assuming nested loops cause O(n²)
• Confusing prefix sums with sliding window
• Thinking auxiliary space affects time complexity

5. Suppose the problem is modified so that elements in the array can be reused any number of times to form contiguous subarrays (i.e., subarrays can wrap around or repeat elements). Which of the following statements about adapting the sliding window algorithm is correct?

hard

A. The original sliding window algorithm works without changes because product updates remain valid with repeated elements.

B. Using a max-heap to track products allows efficient counting of repeated-element subarrays.

C. The sliding window approach fails because the window can grow indefinitely due to element reuse, requiring a different approach like dynamic programming.

D. We can fix the sliding window by resetting the window whenever product exceeds k, but counting subarrays remains the same.

Solution

1. Step 1: Understand element reuse impact

   Allowing reuse means subarrays can be infinitely long by repeating elements, so the window can grow without bound.

2. Step 2: Sliding window limitation

   Sliding window relies on finite array length and shrinking window when product exceeds k; infinite repetition breaks this logic.

3. Step 3: Alternative approach needed

   Dynamic programming or other methods are needed to handle infinite or repeated elements properly.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Infinite growth breaks sliding window assumptions -> need different approach [OK]

Hint: Infinite repetition breaks sliding window shrinking logic [OK]

Common Mistakes:

• Assuming sliding window works unchanged
• Trying to fix by resets only