Longest Substring Without Repeating Characters

🎯

Longest Substring Without Repeating Characters

mediumSLIDING_WINDOWAmazonFacebookGoogle

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.

💡 This problem asks for the longest substring without repeating characters, which is tricky because beginners often try to check all substrings naively, leading to inefficient solutions. Understanding how to efficiently track and update the substring boundaries is key.

📋

Problem Statement

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

💡

Example

Input"abcabcbb"

Output3

The answer is 'abc', with length 3.

Input"bbbbb"

Output1

The answer is 'b', with length 1.

Input"pwwkew"

Output3

The answer is 'wke', with length 3. Note that 'pwke' is a subsequence, not a substring.

• Empty string → 0
• String with all unique characters → length of entire string
• String with all identical characters → 1
• String with special characters and spaces → correctly handle all characters

⚠️

Common Mistakes

Not updating left pointer correctly when duplicate found

Leads to incorrect window size and wrong answer

✅ Ensure left pointer moves to max of current left and last duplicate index + 1

Using a hash set but not shrinking window properly

Infinite loop or incorrect results due to duplicates not removed

✅ Use a while loop to remove characters until duplicate is gone

Checking uniqueness by sorting substring repeatedly

Leads to high time complexity and TLE

✅ Use hash set or hashmap to check duplicates in O(1)

Confusing substring and subsequence in explanation

Miscommunication with interviewer and incorrect problem understanding

✅ Clarify substring means contiguous characters, subsequence can be non-contiguous

🧠

Brute Force (Check All Substrings)

💡 This approach exists to build intuition by trying every possible substring and checking if it has duplicates, which is straightforward but inefficient.

Intuition

Try every substring and check if it contains all unique characters. Keep track of the maximum length found.

Algorithm

1. Generate all possible substrings of the input string.
2. For each substring, check if all characters are unique.
3. Keep track of the length of the longest substring with unique characters.
4. Return the maximum length found.

💡 This algorithm is easy to understand but hard to optimize because it checks many overlapping substrings repeatedly.

</>

Code

def lengthOfLongestSubstring(s: str) -> int:
    max_len = 0
    n = len(s)
    for i in range(n):
        for j in range(i + 1, n + 1):
            substring = s[i:j]
            if len(set(substring)) == len(substring):
                max_len = max(max_len, j - i)
    return max_len

# Driver code
if __name__ == '__main__':
    test_str = "abcabcbb"
    print(lengthOfLongestSubstring(test_str))  # Expected output: 3

Line Notes

max_len = 0Initialize max_len to track the longest substring length found so far

for i in range(n)Outer loop selects the start index of the substring

for j in range(i + 1, n + 1)Inner loop selects the end index (exclusive) of the substring

if len(set(substring)) == len(substring)Check if all characters in substring are unique by comparing set size

max_len = max(max_len, j - i)Update max_len if current substring is longer

return max_lenReturn the maximum length found after checking all substrings

public class Solution {
    public static int lengthOfLongestSubstring(String s) {
        int maxLen = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= n; j++) {
                String substring = s.substring(i, j);
                if (allUnique(substring)) {
                    maxLen = Math.max(maxLen, j - i);
                }
            }
        }
        return maxLen;
    }

    private static boolean allUnique(String s) {
        Set<Character> set = new HashSet<>();
        for (char c : s.toCharArray()) {
            if (set.contains(c)) return false;
            set.add(c);
        }
        return true;
    }

    public static void main(String[] args) {
        String testStr = "abcabcbb";
        System.out.println(lengthOfLongestSubstring(testStr)); // Expected output: 3
    }
}

Line Notes

int maxLen = 0;Initialize maxLen to track the longest substring length found

for (int i = 0; i < n; i++)Outer loop selects the start index of the substring

for (int j = i + 1; j <= n; j++)Inner loop selects the end index (exclusive) of the substring

String substring = s.substring(i, j);Extract substring from i to j-1

if (allUnique(substring))Check if substring has all unique characters

maxLen = Math.max(maxLen, j - i);Update maxLen if current substring is longer

return maxLen;Return the maximum length found after checking all substrings

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

bool allUnique(const string& s) {
    unordered_set<char> set;
    for (char c : s) {
        if (set.count(c)) return false;
        set.insert(c);
    }
    return true;
}

int lengthOfLongestSubstring(string s) {
    int maxLen = 0;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            string substring = s.substr(i, j - i);
            if (allUnique(substring)) {
                maxLen = max(maxLen, j - i);
            }
        }
    }
    return maxLen;
}

int main() {
    string testStr = "abcabcbb";
    cout << lengthOfLongestSubstring(testStr) << endl; // Expected output: 3
    return 0;
}

Line Notes

int maxLen = 0;Initialize maxLen to track the longest substring length found

for (int i = 0; i < n; i++)Outer loop selects the start index of the substring

for (int j = i + 1; j <= n; j++)Inner loop selects the end index (exclusive) of the substring

string substring = s.substr(i, j - i);Extract substring from i to j-1

if (allUnique(substring))Check if substring has all unique characters

maxLen = max(maxLen, j - i);Update maxLen if current substring is longer

return maxLen;Return the maximum length found after checking all substrings

function lengthOfLongestSubstring(s) {
    let maxLen = 0;
    const n = s.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j <= n; j++) {
            const substring = s.substring(i, j);
            if (allUnique(substring)) {
                maxLen = Math.max(maxLen, j - i);
            }
        }
    }
    return maxLen;
}

function allUnique(s) {
    const set = new Set();
    for (const char of s) {
        if (set.has(char)) return false;
        set.add(char);
    }
    return true;
}

// Test
console.log(lengthOfLongestSubstring("abcabcbb")); // Expected output: 3

Line Notes

let maxLen = 0;Initialize maxLen to track the longest substring length found

for (let i = 0; i < n; i++)Outer loop selects the start index of the substring

for (let j = i + 1; j <= n; j++)Inner loop selects the end index (exclusive) of the substring

const substring = s.substring(i, j);Extract substring from i to j-1

if (allUnique(substring))Check if substring has all unique characters

maxLen = Math.max(maxLen, j - i);Update maxLen if current substring is longer

return maxLen;Return the maximum length found after checking all substrings

⏱

Complexity

TimeO(n^3)

SpaceO(n)

There are O(n^2) substrings and checking uniqueness takes O(n) time each, leading to O(n^3) total time.

💡 For n=20, this means about 8000 operations per substring check, totaling millions of operations, which is too slow for large inputs.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and motivate better solutions.

🧠

Sliding Window with HashSet

💡 This approach improves efficiency by using a sliding window and a hash set to track characters in the current window, avoiding repeated checks of all substrings.

Intuition

Use two pointers to represent a window and expand it while characters are unique. If a duplicate is found, shrink the window from the left until the duplicate is removed.

Algorithm

1. Initialize two pointers (left and right) at the start of the string and an empty hash set.
2. Expand the right pointer, adding characters to the set if not already present.
3. If a duplicate character is found, move the left pointer forward, removing characters from the set until the duplicate is removed.
4. Track the maximum window size during the process.
5. Return the maximum size found.

💡 This algorithm efficiently maintains a window of unique characters by dynamically adjusting boundaries, which can be tricky to implement correctly at first.

</>

Code

def lengthOfLongestSubstring(s: str) -> int:
    char_set = set()
    left = 0
    max_len = 0
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    return max_len

# Driver code
if __name__ == '__main__':
    test_str = "abcabcbb"
    print(lengthOfLongestSubstring(test_str))  # Expected output: 3

Line Notes

char_set = set()Initialize a set to store unique characters in the current window

left = 0Left pointer starts at the beginning of the string

for right in range(len(s))Right pointer expands the window by moving forward

while s[right] in char_setIf current character is duplicate, shrink window from left

char_set.remove(s[left])Remove character at left pointer to eliminate duplicate

left += 1Move left pointer forward to shrink window

char_set.add(s[right])Add current character to the set as it's now unique in window

max_len = max(max_len, right - left + 1)Update max_len with current window size

import java.util.HashSet;

public class Solution {
    public static int lengthOfLongestSubstring(String s) {
        HashSet<Character> set = new HashSet<>();
        int left = 0, maxLen = 0;
        for (int right = 0; right < s.length(); right++) {
            while (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left));
                left++;
            }
            set.add(s.charAt(right));
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        String testStr = "abcabcbb";
        System.out.println(lengthOfLongestSubstring(testStr)); // Expected output: 3
    }
}

Line Notes

HashSet<Character> set = new HashSet<>();Initialize a set to store unique characters in the current window

int left = 0, maxLen = 0;Left pointer and maxLen initialization

for (int right = 0; right < s.length(); right++)Right pointer expands the window

while (set.contains(s.charAt(right)))If duplicate found, shrink window from left

set.remove(s.charAt(left));Remove character at left pointer to remove duplicate

left++;Move left pointer forward

set.add(s.charAt(right));Add current character to the set

maxLen = Math.max(maxLen, right - left + 1);Update maxLen with current window size

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int lengthOfLongestSubstring(string s) {
    unordered_set<char> set;
    int left = 0, maxLen = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        while (set.count(s[right])) {
            set.erase(s[left]);
            left++;
        }
        set.insert(s[right]);
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

int main() {
    string testStr = "abcabcbb";
    cout << lengthOfLongestSubstring(testStr) << endl; // Expected output: 3
    return 0;
}

Line Notes

unordered_set<char> set;Initialize a set to store unique characters in the current window

int left = 0, maxLen = 0;Initialize left pointer and maxLen

for (int right = 0; right < (int)s.size(); right++)Right pointer expands the window

while (set.count(s[right]))If duplicate character found, shrink window from left

set.erase(s[left]);Remove character at left pointer to remove duplicate

left++;Move left pointer forward

set.insert(s[right]);Add current character to the set

maxLen = max(maxLen, right - left + 1);Update maxLen with current window size

function lengthOfLongestSubstring(s) {
    const set = new Set();
    let left = 0, maxLen = 0;
    for (let right = 0; right < s.length; right++) {
        while (set.has(s[right])) {
            set.delete(s[left]);
            left++;
        }
        set.add(s[right]);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

// Test
console.log(lengthOfLongestSubstring("abcabcbb")); // Expected output: 3

Line Notes

const set = new Set();Initialize a set to store unique characters in the current window

let left = 0, maxLen = 0;Initialize left pointer and maxLen

for (let right = 0; right < s.length; right++)Right pointer expands the window

while (set.has(s[right]))If duplicate character found, shrink window from left

set.delete(s[left]);Remove character at left pointer to remove duplicate

left++;Move left pointer forward

set.add(s[right]);Add current character to the set

maxLen = Math.max(maxLen, right - left + 1);Update maxLen with current window size

⏱

Complexity

TimeO(n)

SpaceO(min(m, n)) where m is character set size

Each character is visited at most twice by left and right pointers, so linear time. Space depends on unique characters in window.

💡 For n=10^5, this means about 200,000 operations, which is efficient and scalable.

Interview Verdict: Accepted

This approach is efficient and commonly accepted in interviews for this problem.

🧠

Optimized Sliding Window with HashMap (Index Tracking)

💡 This approach further optimizes by using a hashmap to jump the left pointer directly past duplicates, avoiding incremental shrinking.

Intuition

Use a hashmap to store the last index of each character. When a duplicate is found, move the left pointer to the index after the previous occurrence of that character.

Algorithm

1. Initialize a hashmap to store characters and their latest indices.
2. Use two pointers, left and right, to represent the window.
3. For each character at right, if it is in the hashmap and its index is >= left, move left to index + 1.
4. Update the hashmap with the current character's index.
5. Track the maximum window size during iteration.
6. Return the maximum size found.

💡 This algorithm cleverly skips over duplicates by jumping the left pointer, which can be subtle to implement correctly.

</>

Code

def lengthOfLongestSubstring(s: str) -> int:
    index_map = {}
    max_len = 0
    left = 0
    for right, char in enumerate(s):
        if char in index_map and index_map[char] >= left:
            left = index_map[char] + 1
        index_map[char] = right
        max_len = max(max_len, right - left + 1)
    return max_len

# Driver code
if __name__ == '__main__':
    test_str = "abcabcbb"
    print(lengthOfLongestSubstring(test_str))  # Expected output: 3

Line Notes

index_map = {}Initialize hashmap to store last seen indices of characters

max_len = 0Initialize max_len to track longest substring length

left = 0Left pointer starts at beginning

for right, char in enumerate(s)Right pointer iterates over characters with index

if char in index_map and index_map[char] >= leftIf duplicate character inside current window, move left pointer

left = index_map[char] + 1Jump left pointer to one position after previous occurrence

index_map[char] = rightUpdate last seen index of current character

max_len = max(max_len, right - left + 1)Update max_len with current window size

import java.util.HashMap;

public class Solution {
    public static int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int maxLen = 0, left = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (map.containsKey(c) && map.get(c) >= left) {
                left = map.get(c) + 1;
            }
            map.put(c, right);
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        String testStr = "abcabcbb";
        System.out.println(lengthOfLongestSubstring(testStr)); // Expected output: 3
    }
}

Line Notes

HashMap<Character, Integer> map = new HashMap<>();Initialize hashmap to store last seen indices

int maxLen = 0, left = 0;Initialize maxLen and left pointer

for (int right = 0; right < s.length(); right++)Right pointer iterates over string

char c = s.charAt(right);Current character at right pointer

if (map.containsKey(c) && map.get(c) >= left)Check if duplicate character inside current window

left = map.get(c) + 1;Jump left pointer to one position after previous occurrence

map.put(c, right);Update last seen index of current character

maxLen = Math.max(maxLen, right - left + 1);Update maxLen with current window size

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> index_map;
    int maxLen = 0, left = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        char c = s[right];
        if (index_map.count(c) && index_map[c] >= left) {
            left = index_map[c] + 1;
        }
        index_map[c] = right;
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

int main() {
    string testStr = "abcabcbb";
    cout << lengthOfLongestSubstring(testStr) << endl; // Expected output: 3
    return 0;
}

Line Notes

unordered_map<char, int> index_map;Initialize hashmap to store last seen indices

int maxLen = 0, left = 0;Initialize maxLen and left pointer

for (int right = 0; right < (int)s.size(); right++)Right pointer iterates over string

char c = s[right];Current character at right pointer

if (index_map.count(c) && index_map[c] >= left)Check if duplicate character inside current window

left = index_map[c] + 1;Jump left pointer to one position after previous occurrence

index_map[c] = right;Update last seen index of current character

maxLen = max(maxLen, right - left + 1);Update maxLen with current window size

function lengthOfLongestSubstring(s) {
    const indexMap = new Map();
    let maxLen = 0, left = 0;
    for (let right = 0; right < s.length; right++) {
        const c = s[right];
        if (indexMap.has(c) && indexMap.get(c) >= left) {
            left = indexMap.get(c) + 1;
        }
        indexMap.set(c, right);
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

// Test
console.log(lengthOfLongestSubstring("abcabcbb")); // Expected output: 3

Line Notes

const indexMap = new Map();Initialize hashmap to store last seen indices

let maxLen = 0, left = 0;Initialize maxLen and left pointer

for (let right = 0; right < s.length; right++)Right pointer iterates over string

const c = s[right];Current character at right pointer

if (indexMap.has(c) && indexMap.get(c) >= left)Check if duplicate character inside current window

left = indexMap.get(c) + 1;Jump left pointer to one position after previous occurrence

indexMap.set(c, right);Update last seen index of current character

maxLen = Math.max(maxLen, right - left + 1);Update maxLen with current window size

⏱

Complexity

TimeO(n)

SpaceO(min(m, n)) where m is character set size

Each character is processed once, and left pointer jumps forward, so linear time. Space depends on unique characters.

💡 For large inputs, this approach is optimal and avoids unnecessary steps compared to the previous sliding window.

Interview Verdict: Accepted

This is the most optimal and clean solution for this problem in interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, code the optimized sliding window with hashmap approach for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^3)	O(n)	No	N/A	Mention only - never code
2. Sliding Window with HashSet	O(n)	O(min(m, n))	No	N/A	Good for explaining sliding window concept
3. Optimized Sliding Window with HashMap	O(n)	O(min(m, n))	No	N/A	Code this for optimal solution

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and ask about input constraints.Explain the brute force approach to show understanding.Discuss inefficiencies and introduce sliding window with hash set.Optimize further using a hashmap to jump left pointer.Code the optimal solution carefully and test edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize from brute force to sliding window, and coding accuracy with edge cases.

Common Follow-ups

• What if the input contains Unicode characters? → Use a hashmap instead of fixed-size arrays.
• Can you return the substring itself, not just the length? → Track start index of max substring.

💡 These follow-ups test your ability to adapt the solution to variations and extend functionality.

🔍

Pattern Recognition

When to Use

1) Asked for longest/shortest substring or subarray 2) Condition involves uniqueness or frequency of elements 3) Input is a string or array 4) Need to find max/min length or count

Signature Phrases

'longest substring without repeating characters''substring with all unique characters'

NOT This Pattern When

Problems asking for subsequences or fixed-size windows are different patterns.

Similar Problems

Longest Substring with At Most K Distinct Characters - similar sliding window with frequency mapMinimum Window Substring - sliding window to find smallest substring containing all chars

Practice

1. You have a row of cards with points on each card. You can pick exactly k cards from either the start or the end of the row to maximize your total points. Which approach guarantees finding the optimal solution efficiently?

easy

A. Use a greedy algorithm that always picks the card with the highest immediate point value from either end.

B. Use a sliding window to find the minimum sum subarray of length n - k and subtract it from the total sum of all cards.

C. Use dynamic programming to consider all combinations of picking cards from the middle of the array.

D. Use a brute force approach that tries all possible combinations of picking k cards from anywhere in the array.

Solution

1. Step 1: Understand the problem constraints

   The problem restricts picking cards only from the start or end, so the chosen cards form a prefix and suffix combination.

2. Step 2: Recognize the sliding window pattern

   Picking k cards from ends is equivalent to removing a contiguous subarray of length n-k from the middle. Finding the minimum sum subarray of length n-k lets us maximize the points from the ends.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sliding window on middle subarray -> optimal and efficient [OK]

Hint: Sliding window on middle subarray finds minimal removal [OK]

Common Mistakes:

• Greedy picking highest immediate card fails on future gains
• Brute force is too slow for large inputs
• DP on middle cards is unnecessary and inefficient

2. You are given two strings s1 and s2. You need to determine if any substring of s2 is a rearrangement (permutation) of s1. Which algorithmic approach guarantees an optimal solution in terms of time complexity?

easy

A. Greedy approach that tries to match characters from s1 in s2 sequentially.

B. Brute force checking all substrings of s2 and comparing frequency maps with s1.

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

D. Sliding window with frequency map and a match count optimization to track when all characters match.

Solution

1. Step 1: Understand problem constraints

   The problem requires checking if any substring of s2 is a permutation of s1, which means the substring must have the same character counts as s1.

2. Step 2: Identify optimal approach

   Brute force (checking all substrings) is O(n*m) and inefficient. Dynamic programming is not suitable here as the problem is about frequency matching, not overlapping subproblems. Greedy fails because character order can differ. Sliding window with frequency map and match count optimization efficiently tracks character matches in O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sliding window with match count tracks matches in O(n) time [OK]

Hint: Sliding window with match count is O(n) and optimal [OK]

Common Mistakes:

• Believing greedy or DP solves this efficiently
• Thinking brute force is acceptable for large inputs

3. What is the time complexity of the optimal sliding window with count matching algorithm for finding all anagrams of p in s, where n = len(s) and m = len(p)?

medium

A. O(n), because the window slides once over s and frequency counts are updated in constant time.

B. O(n * m), because each window requires comparing frequency maps of size m.

C. O(n * 26), because frequency arrays of fixed size 26 are compared at each step.

D. O(n log m), due to sorting substrings during comparison.

Solution

1. Step 1: Identify main loop operations

   The window slides over s once, so O(n) iterations.

2. Step 2: Check frequency updates and comparisons

   Frequency counts are arrays of fixed size 26, updated in O(1) time; matches count updated in O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window with count matching is linear time [OK]

Hint: Fixed alphabet size makes frequency updates O(1) [OK]

Common Mistakes:

• Assuming frequency map comparison is O(m)
• Confusing n*m with n
• Thinking sorting is involved

4. What is the time complexity of the optimized sliding window algorithm that uses filtered characters for the minimum window substring problem, where n is the length of s and m is the length of t?

medium

A. O(n) because each character in s is visited at most twice by the two pointers

B. O(n * m) because for each character in s we check all characters in t

C. O(n + m) because we filter s and then slide over filtered characters

D. O(n^2) because shrinking and expanding the window can cause nested loops

Solution

1. Step 1: Identify main loops

   The algorithm uses two pointers moving over filtered characters, each pointer advances at most n times.

2. Step 2: Analyze filtering and counting

   Filtering s takes O(n), sliding window over filtered characters is O(n) since each character is visited twice max.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer sliding window is linear time [OK]

Hint: Two pointers each move forward at most n times [OK]

Common Mistakes:

• Confusing filtering cost
• Assuming nested loops cause O(n^2)
• Ignoring that each pointer moves only forward

5. Suppose the fruits problem is modified so that you can pick fruits from trees non-contiguously but still want to maximize the total number of fruits collected with at most two fruit types. Which approach correctly solves this variant?

hard

A. Count total occurrences of each fruit type and sum the two largest counts

B. Sort fruits and use two pointers to find longest contiguous segment with two types

C. Use dynamic programming to find longest subsequence with at most two distinct fruits

D. Use the same sliding window approach since it handles at most two fruit types

Solution

1. Step 1: Understand non-contiguous picking

   Since picking is non-contiguous, order does not matter; we want max total fruits of two types.

2. Step 2: Optimal solution is sum of two largest fruit counts

   Count frequency of each fruit type, pick top two counts, sum them for max fruits.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Non-contiguous means subsequence, so frequency sums suffice [OK]

Hint: Non-contiguous -> sum top two fruit counts [OK]

Common Mistakes:

• Applying sliding window to non-contiguous
• Using DP unnecessarily
• Sorting loses subsequence property