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 two strings s and p. You need to find all start indices in s where a substring is an anagram of p. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Brute force checking all substrings of length equal to p and comparing frequency maps.

B. Sliding window with frequency map comparison and count matching optimization.

C. Dynamic programming to build a table of substring matches based on character counts.

D. Greedy approach by sorting each substring and comparing with sorted p.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding all anagrams of p in s efficiently, ideally in linear time.

2. Step 2: Evaluate algorithmic approaches

   Brute force (checking all substrings) is O(n*m), sorting each substring is O(n*m log m), and DP is not naturally suited here. Sliding window with frequency map and count matching optimizes to O(n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window with count matching is known optimal for fixed-size anagram search [OK]

Hint: Sliding window with count matching -> O(n) time [OK]

Common Mistakes:

• Thinking sorting each substring is efficient enough
• Assuming DP applies directly
• Using brute force for large inputs

2. Consider the following Python code implementing the sliding window with count matching optimization to find all anagrams of p in s. What is the final returned list when s = "cbaebabacd" and p = "abc"?

easy

A. [0, 1, 6]

B. [0, 6, 7]

C. [0, 6, 8]

D. [0, 6]

Solution

1. Step 1: Trace first window (indices 0 to 2)

   Substring "cba" is an anagram of "abc", so index 0 is added.

2. Step 2: Slide window and check matches

   Next valid anagram found at index 6 ("bac"). No other windows match all counts.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Known example output matches [0, 6] [OK]

Hint: Anagrams appear at indices 0 and 6 only [OK]

Common Mistakes:

• Including indices where substring is not full anagram
• Off-by-one errors in window boundaries

3. You are given two strings s and t. Your task is to find the shortest substring in s that contains all characters of t including duplicates. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming to build a table of minimum substrings for all prefixes of s and t

B. Greedy approach that expands the window until all characters are found, then shrinks it from the left without tracking counts

C. Sliding window with two pointers and frequency maps to track counts of characters in the current window

D. Sorting both strings and using two pointers to find matching characters in order

Solution

1. Step 1: Understand problem requirements

   The problem requires finding the shortest substring containing all characters of t with correct counts, which demands tracking character frequencies.

2. Step 2: Evaluate algorithm suitability

   Greedy without frequency tracking can miss duplicates; DP is inefficient and not straightforward here; sorting breaks substring order. Sliding window with frequency maps efficiently tracks counts and adjusts window size optimally.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sliding window with frequency maps is the classic optimal approach [OK]

Hint: Track counts with two pointers for optimal substring [OK]

Common Mistakes:

• Assuming greedy without counts works
• Confusing DP with substring problems
• Sorting breaks substring order

4. Consider the following Python code implementing the sliding window maximum using a monotonic deque. What is the returned result when calling maxSlidingWindow([2, 1, 3], 2)?

easy

A. [2, 3]

B. [2, 1, 3]

C. [3]

D. [1, 3]

Solution

1. Step 1: Trace the deque and result for each iteration

   i=0: dq=[0], result=[]; i=1: nums[1]=1 < nums[0]=2, dq=[0,1], result=[]; i=2: nums[2]=3 > nums[1]=1 pop 1, nums[2]=3 > nums[0]=2 pop 0, dq=[2]; after i=1 (window [2,1]) result append nums[0]=2; after i=2 (window [1,3]) result append nums[2]=3.

2. Step 2: Collect final result

   Result after full iteration is [2, 3].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches expected sliding window maximum for windows [2,1] and [1,3] [OK]

Hint: Deque stores indices of max candidates, popping smaller elements [OK]

Common Mistakes:

• Appending result before window is full
• Not removing indices outside the window
• Confusing values and indices in deque

5. Identify the bug in the following code snippet for the Maximum Points You Can Obtain from Cards problem:

medium

A. Line 7: Loop range should start from k instead of window_size.

B. Line 4: Incorrect initial sum calculation; should sum last k elements instead of first window_size.

C. Line 9: The condition should be current_sum > min_subarray_sum instead of <.

D. Line 3: Incorrect calculation of window_size; should be n - k instead of k.

Solution

1. Step 1: Understand window size meaning

   The window represents the subarray to exclude, which must be length n - k, not k.

2. Step 2: Identify impact of wrong window size

   Using k as window size causes the algorithm to exclude wrong subarray length, leading to incorrect results.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct window size is n - k for the sliding window [OK]

Hint: Window size must be n - k, not k [OK]

Common Mistakes:

• Confusing window size with k instead of n-k
• Incorrect loop boundaries
• Wrong comparison operator in min update