Longest Substring with At Most K Distinct Characters

🎯

Longest Substring with At Most K Distinct Characters

mediumSLIDING_WINDOWAmazonGoogle

Imagine you're analyzing a stream of characters from a social media feed and want to find the longest segment where the diversity of topics (characters) is limited to at most K distinct ones.

💡 This problem is a classic example of using a sliding window to handle substrings with constraints. Beginners often struggle because they try to check every substring naively, which is inefficient, and miss the insight that a variable-size window with a frequency map can solve it optimally.

📋

Problem Statement

Given a string s and an integer k, find the length of the longest substring of s that contains at most k distinct characters. Return the length of such substring.

1 ≤ s.length ≤ 10^50 ≤ k ≤ s.lengths consists of English letters, digits, symbols, and spaces.

💡

Example

Input"s = 'eceba', k = 2"

Output3

The longest substring with at most 2 distinct characters is 'ece' with length 3.

Input"s = 'aa', k = 1"

Output2

The longest substring with at most 1 distinct character is 'aa' itself.

• k = 0 → output should be 0 because no characters allowed
• s is empty string → output should be 0
• k >= length of s → output should be length of s
• string with all identical characters → output should be length of s

⚠️

Common Mistakes

Not shrinking the window when distinct characters exceed k

Code returns incorrect longer substrings violating constraints

✅ Add a while loop to shrink the window until distinct chars ≤ k

Using a set instead of a frequency map

Cannot correctly track when to remove characters, leading to wrong counts

✅ Use a frequency map/dictionary to track counts of each character

Not handling k=0 or empty string edge cases

Code may crash or return wrong results

✅ Add explicit checks for k=0 or empty input at the start

Updating max_length before shrinking window

May count invalid windows with too many distinct characters

✅ Update max_length only after ensuring window is valid (distinct chars ≤ k)

Using unordered data structures that don't maintain insertion order when needed

Cannot efficiently remove the oldest character in some approaches

✅ Use ordered dictionaries or linked hash maps when order matters

🧠

Brute Force (Check All Substrings)

💡 This approach exists to build intuition by trying every possible substring and checking if it meets the condition. It is simple but inefficient, helping beginners understand the problem's requirements before optimizing.

Intuition

Try every substring of s, count distinct characters, and track the longest substring with at most k distinct characters.

Algorithm

1. Initialize max_length to 0.
2. For each start index i in s:
3. For each end index j from i to end of s:
4. Extract substring s[i:j+1], count distinct characters.
5. If distinct characters ≤ k, update max_length if this substring is longer.

💡 The nested loops and counting distinct characters inside the inner loop make this approach slow and hard to optimize directly.

</>

Code

def length_of_longest_substring_k_distinct(s: str, k: int) -> int:
    max_length = 0
    n = len(s)
    for i in range(n):
        distinct_chars = set()
        for j in range(i, n):
            distinct_chars.add(s[j])
            if len(distinct_chars) > k:
                break
            max_length = max(max_length, j - i + 1)
    return max_length

# Driver code
if __name__ == '__main__':
    print(length_of_longest_substring_k_distinct('eceba', 2))  # Expected: 3

Line Notes

max_length = 0Initialize the variable to keep track of the longest valid substring found so far

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

distinct_chars = set()Use a set to track distinct characters in the current substring

for j in range(i, n)Inner loop extends the substring to the right

distinct_chars.add(s[j])Add the current character to the set to track distinct characters

if len(distinct_chars) > kIf distinct characters exceed k, stop expanding this substring

max_length = max(max_length, j - i + 1)Update max_length if current substring is longer

return max_lengthReturn the length of the longest valid substring found

import java.util.*;
public class Solution {
    public static int lengthOfLongestSubstringKDistinct(String s, int k) {
        int maxLength = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            Set<Character> distinctChars = new HashSet<>();
            for (int j = i; j < n; j++) {
                distinctChars.add(s.charAt(j));
                if (distinctChars.size() > k) {
                    break;
                }
                maxLength = Math.max(maxLength, j - i + 1);
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstringKDistinct("eceba", 2)); // Expected: 3
    }
}

Line Notes

int maxLength = 0;Initialize maxLength to track longest substring length

for (int i = 0; i < n; i++)Outer loop picks start index

Set<Character> distinctChars = new HashSet<>();Track distinct characters in current substring

for (int j = i; j < n; j++)Inner loop extends substring to the right

distinctChars.add(s.charAt(j));Add current character to set

if (distinctChars.size() > k)Stop if distinct characters exceed k

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

return maxLength;Return the longest valid substring length

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

int lengthOfLongestSubstringKDistinct(string s, int k) {
    int maxLength = 0;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        unordered_set<char> distinctChars;
        for (int j = i; j < n; j++) {
            distinctChars.insert(s[j]);
            if ((int)distinctChars.size() > k) {
                break;
            }
            maxLength = max(maxLength, j - i + 1);
        }
    }
    return maxLength;
}

int main() {
    cout << lengthOfLongestSubstringKDistinct("eceba", 2) << endl; // Expected: 3
    return 0;
}

Line Notes

int maxLength = 0;Initialize maxLength to store longest substring length

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

unordered_set<char> distinctChars;Set to track distinct characters in substring

for (int j = i; j < n; j++)Inner loop extends substring

distinctChars.insert(s[j]);Add character to set

if ((int)distinctChars.size() > k)Break if distinct chars exceed k

maxLength = max(maxLength, j - i + 1);Update maxLength if current substring is longer

return maxLength;Return the longest valid substring length

function lengthOfLongestSubstringKDistinct(s, k) {
    let maxLength = 0;
    const n = s.length;
    for (let i = 0; i < n; i++) {
        const distinctChars = new Set();
        for (let j = i; j < n; j++) {
            distinctChars.add(s[j]);
            if (distinctChars.size > k) {
                break;
            }
            maxLength = Math.max(maxLength, j - i + 1);
        }
    }
    return maxLength;
}

// Test
console.log(lengthOfLongestSubstringKDistinct('eceba', 2)); // Expected: 3

Line Notes

let maxLength = 0;Initialize maxLength to track longest substring length

for (let i = 0; i < n; i++)Outer loop picks start index

const distinctChars = new Set();Set to track distinct characters in substring

for (let j = i; j < n; j++)Inner loop extends substring

distinctChars.add(s[j]);Add current character to set

if (distinctChars.size > k)Stop if distinct characters exceed k

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

return maxLength;Return the longest valid substring length

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Two nested loops generate all substrings (O(n^2)), and counting distinct characters uses a set that can be up to O(n) in size.

💡 For n=20, this means about 400 substring checks, each with set operations, which is manageable but grows quickly for larger n.

Interview Verdict: TLE for large inputs

This approach is too slow for large inputs but is useful to understand the problem and correctness before optimizing.

🧠

Sliding Window with Frequency Map (Two Pointers)

💡 This approach improves efficiency by using two pointers to maintain a window and a frequency map to track character counts, avoiding re-counting distinct characters repeatedly.

Intuition

Expand the right pointer to include characters until the window has more than k distinct characters, then move the left pointer to shrink the window until it satisfies the constraint again.

Algorithm

1. Initialize two pointers left and right at 0, max_length = 0.
2. Use a hashmap/dictionary to count character frequencies in the current window.
3. Expand right pointer, add character frequency.
4. While distinct characters > k, shrink window from left, decrement frequency, remove char if frequency is zero.
5. Update max_length with current window size if valid.

💡 The key is maintaining the frequency map and adjusting the window size dynamically to keep distinct chars ≤ k.

</>

Code

def length_of_longest_substring_k_distinct(s: str, k: int) -> int:
    if k == 0 or not s:
        return 0
    left = 0
    max_length = 0
    freq = {}
    for right in range(len(s)):
        freq[s[right]] = freq.get(s[right], 0) + 1
        while len(freq) > k:
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1
        max_length = max(max_length, right - left + 1)
    return max_length

# Driver code
if __name__ == '__main__':
    print(length_of_longest_substring_k_distinct('eceba', 2))  # Expected: 3

Line Notes

if k == 0 or not s:Handle edge cases where no characters allowed or empty string

left = 0Initialize left pointer of sliding window

freq = {}Dictionary to store frequency of characters in current window

for right in range(len(s))Expand right pointer to include new characters

freq[s[right]] = freq.get(s[right], 0) + 1Increment frequency count for current character

while len(freq) > kShrink window from left if distinct chars exceed k

freq[s[left]] -= 1Decrease frequency of leftmost character

if freq[s[left]] == 0: del freq[s[left]]Remove character from map if frequency zero

left += 1Move left pointer to shrink window

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

return max_lengthReturn the longest valid substring length

import java.util.*;
public class Solution {
    public static int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (k == 0 || s.length() == 0) return 0;
        Map<Character, Integer> freq = new HashMap<>();
        int left = 0, maxLength = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            freq.put(c, freq.getOrDefault(c, 0) + 1);
            while (freq.size() > k) {
                char leftChar = s.charAt(left);
                freq.put(leftChar, freq.get(leftChar) - 1);
                if (freq.get(leftChar) == 0) {
                    freq.remove(leftChar);
                }
                left++;
            }
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstringKDistinct("eceba", 2)); // Expected: 3
    }
}

Line Notes

if (k == 0 || s.length() == 0) return 0;Handle edge cases early

Map<Character, Integer> freq = new HashMap<>();Frequency map to track characters in window

int left = 0, maxLength = 0;Initialize pointers and max length

for (int right = 0; right < s.length(); right++)Expand right pointer

freq.put(c, freq.getOrDefault(c, 0) + 1);Increment frequency of current character

while (freq.size() > k)Shrink window if distinct chars exceed k

freq.put(leftChar, freq.get(leftChar) - 1);Decrease frequency of leftmost character

if (freq.get(leftChar) == 0) freq.remove(leftChar);Remove character if frequency zero

left++;Move left pointer to shrink window

maxLength = Math.max(maxLength, right - left + 1);Update max length

return maxLength;Return longest valid substring length

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

int lengthOfLongestSubstringKDistinct(string s, int k) {
    if (k == 0 || s.empty()) return 0;
    unordered_map<char, int> freq;
    int left = 0, maxLength = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        freq[s[right]]++;
        while ((int)freq.size() > k) {
            freq[s[left]]--;
            if (freq[s[left]] == 0) {
                freq.erase(s[left]);
            }
            left++;
        }
        maxLength = max(maxLength, right - left + 1);
    }
    return maxLength;
}

int main() {
    cout << lengthOfLongestSubstringKDistinct("eceba", 2) << endl; // Expected: 3
    return 0;
}

Line Notes

if (k == 0 || s.empty()) return 0;Handle edge cases early

unordered_map<char, int> freq;Frequency map for characters in window

int left = 0, maxLength = 0;Initialize pointers and max length

for (int right = 0; right < (int)s.size(); right++)Expand right pointer

freq[s[right]]++;Increment frequency of current character

while ((int)freq.size() > k)Shrink window if distinct chars exceed k

freq[s[left]]--;Decrease frequency of leftmost character

if (freq[s[left]] == 0) freq.erase(s[left]);Remove character if frequency zero

left++;Move left pointer to shrink window

maxLength = max(maxLength, right - left + 1);Update max length

return maxLength;Return longest valid substring length

function lengthOfLongestSubstringKDistinct(s, k) {
    if (k === 0 || s.length === 0) return 0;
    let freq = new Map();
    let left = 0, maxLength = 0;
    for (let right = 0; right < s.length; right++) {
        freq.set(s[right], (freq.get(s[right]) || 0) + 1);
        while (freq.size > k) {
            freq.set(s[left], freq.get(s[left]) - 1);
            if (freq.get(s[left]) === 0) {
                freq.delete(s[left]);
            }
            left++;
        }
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

// Test
console.log(lengthOfLongestSubstringKDistinct('eceba', 2)); // Expected: 3

Line Notes

if (k === 0 || s.length === 0) return 0;Handle edge cases early

let freq = new Map();Map to track character frequencies

let left = 0, maxLength = 0;Initialize pointers and max length

for (let right = 0; right < s.length; right++)Expand right pointer

freq.set(s[right], (freq.get(s[right]) || 0) + 1);Increment frequency of current character

while (freq.size > k)Shrink window if distinct chars exceed k

freq.set(s[left], freq.get(s[left]) - 1);Decrease frequency of leftmost character

if (freq.get(s[left]) === 0) freq.delete(s[left]);Remove character if frequency zero

left++;Move left pointer to shrink window

maxLength = Math.max(maxLength, right - left + 1);Update max length

return maxLength;Return longest valid substring length

⏱

Complexity

TimeO(n)

SpaceO(k)

Each character is visited at most twice by left and right pointers, and frequency map size is at most k.

💡 For n=20 and k=2, this means about 40 operations plus small map updates, which is very efficient.

Interview Verdict: Accepted

This is the optimal approach for this problem and passes all test cases efficiently.

🧠

Sliding Window with Ordered Dictionary (Maintaining Last Seen Index)

💡 This approach uses an ordered dictionary (or linked hash map) to track the last occurrence of each character, allowing quick removal of the leftmost character when distinct count exceeds k.

Intuition

Keep track of characters and their last indices in insertion order. When distinct characters exceed k, remove the leftmost character by its last seen index to shrink the window.

Algorithm

1. Initialize left pointer and max_length to 0.
2. Use an ordered dictionary to store characters and their last indices.
3. Expand right pointer, update character's last index in dictionary.
4. If dictionary size exceeds k, remove the leftmost character and move left pointer to one past its last index.
5. Update max_length with current window size.

💡 The ordered dictionary helps efficiently identify and remove the oldest character to maintain the constraint.

</>

Code

from collections import OrderedDict

def length_of_longest_substring_k_distinct(s: str, k: int) -> int:
    if k == 0 or not s:
        return 0
    left = 0
    max_length = 0
    last_seen = OrderedDict()
    for right, char in enumerate(s):
        if char in last_seen:
            del last_seen[char]
        last_seen[char] = right
        if len(last_seen) > k:
            _, idx = last_seen.popitem(last=False)
            left = idx + 1
        max_length = max(max_length, right - left + 1)
    return max_length

# Driver code
if __name__ == '__main__':
    print(length_of_longest_substring_k_distinct('eceba', 2))  # Expected: 3

Line Notes

from collections import OrderedDictImport OrderedDict to maintain insertion order of keys

last_seen = OrderedDict()Stores characters and their last seen indices in order

if char in last_seen: del last_seen[char]Remove char to update its position in order

last_seen[char] = rightInsert char with current index as last seen

if len(last_seen) > kIf distinct chars exceed k, remove oldest

_, idx = last_seen.popitem(last=False)Pop the first inserted character and get its index

left = idx + 1Move left pointer to one past removed character's index

max_length = max(max_length, right - left + 1)Update max length

return max_lengthReturn longest valid substring length

import java.util.*;
public class Solution {
    public static int lengthOfLongestSubstringKDistinct(String s, int k) {
        if (k == 0 || s.length() == 0) return 0;
        LinkedHashMap<Character, Integer> lastSeen = new LinkedHashMap<>();
        int left = 0, maxLength = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (lastSeen.containsKey(c)) {
                lastSeen.remove(c);
            }
            lastSeen.put(c, right);
            if (lastSeen.size() > k) {
                Map.Entry<Character, Integer> firstEntry = lastSeen.entrySet().iterator().next();
                int idx = firstEntry.getValue();
                lastSeen.remove(firstEntry.getKey());
                left = idx + 1;
            }
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstringKDistinct("eceba", 2)); // Expected: 3
    }
}

Line Notes

LinkedHashMap<Character, Integer> lastSeen = new LinkedHashMap<>();Maintain insertion order of characters and their last indices

if (lastSeen.containsKey(c)) lastSeen.remove(c);Remove character to update its position

lastSeen.put(c, right);Insert character with current index

if (lastSeen.size() > k)If distinct chars exceed k, remove oldest

Map.Entry<Character, Integer> firstEntry = lastSeen.entrySet().iterator().next();Get oldest character entry

lastSeen.remove(firstEntry.getKey());Remove oldest character

left = idx + 1;Move left pointer past removed character

maxLength = Math.max(maxLength, right - left + 1);Update max length

return maxLength;Return longest valid substring length

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

int lengthOfLongestSubstringKDistinct(string s, int k) {
    if (k == 0 || s.empty()) return 0;
    list<pair<char, int>> lastSeenList;
    unordered_map<char, list<pair<char, int>>::iterator> lastSeenMap;
    int left = 0, maxLength = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        char c = s[right];
        if (lastSeenMap.find(c) != lastSeenMap.end()) {
            lastSeenList.erase(lastSeenMap[c]);
        }
        lastSeenList.push_back({c, right});
        lastSeenMap[c] = prev(lastSeenList.end());
        if ((int)lastSeenList.size() > k) {
            auto front = lastSeenList.front();
            lastSeenMap.erase(front.first);
            left = front.second + 1;
            lastSeenList.pop_front();
        }
        maxLength = max(maxLength, right - left + 1);
    }
    return maxLength;
}

int main() {
    cout << lengthOfLongestSubstringKDistinct("eceba", 2) << endl; // Expected: 3
    return 0;
}

Line Notes

list<pair<char, int>> lastSeenList;Doubly linked list to maintain order of characters and indices

unordered_map<char, list<pair<char, int>>::iterator> lastSeenMap;Map to quickly find and remove characters from list

if (lastSeenMap.find(c) != lastSeenMap.end()) lastSeenList.erase(lastSeenMap[c]);Remove character to update its position

lastSeenList.push_back({c, right});Add character with current index at end

lastSeenMap[c] = prev(lastSeenList.end());Update map with iterator to new position

if ((int)lastSeenList.size() > k)If distinct chars exceed k, remove oldest

auto front = lastSeenList.front();Get oldest character and index

lastSeenMap.erase(front.first);Remove from map

left = front.second + 1;Move left pointer past removed character

lastSeenList.pop_front();Remove oldest character from list

maxLength = max(maxLength, right - left + 1);Update max length

return maxLength;Return longest valid substring length

function lengthOfLongestSubstringKDistinct(s, k) {
    if (k === 0 || s.length === 0) return 0;
    const lastSeen = new Map();
    let left = 0, maxLength = 0;
    for (let right = 0; right < s.length; right++) {
        const c = s[right];
        if (lastSeen.has(c)) {
            lastSeen.delete(c);
        }
        lastSeen.set(c, right);
        if (lastSeen.size > k) {
            const firstKey = lastSeen.keys().next().value;
            const idx = lastSeen.get(firstKey);
            lastSeen.delete(firstKey);
            left = idx + 1;
        }
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

// Test
console.log(lengthOfLongestSubstringKDistinct('eceba', 2)); // Expected: 3

Line Notes

if (k === 0 || s.length === 0) return 0;Handle edge cases early

const lastSeen = new Map();Map to maintain insertion order and last indices

if (lastSeen.has(c)) lastSeen.delete(c);Remove character to update its position

lastSeen.set(c, right);Insert character with current index

if (lastSeen.size > k)If distinct chars exceed k, remove oldest

const firstKey = lastSeen.keys().next().value;Get oldest character key

const idx = lastSeen.get(firstKey);Get last index of oldest character

lastSeen.delete(firstKey);Remove oldest character

left = idx + 1;Move left pointer past removed character

maxLength = Math.max(maxLength, right - left + 1);Update max length

return maxLength;Return longest valid substring length

⏱

Complexity

TimeO(n)

SpaceO(k)

Each character is processed once, and the ordered dictionary/map operations are O(1) average. The window adjusts dynamically.

💡 This approach is similar in efficiency to the frequency map method but uses order to quickly evict the oldest character.

Interview Verdict: Accepted

This approach is optimal and useful when you want to quickly identify and remove the oldest character in the window.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, coding the sliding window with frequency map approach is best because it is optimal and straightforward.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	N/A	Mention only - never code due to inefficiency
2. Sliding Window with Frequency Map	O(n)	O(k)	No	Yes	Code this approach for optimal solution
3. Sliding Window with Ordered Dictionary	O(n)	O(k)	No	Yes	Mention as alternative or if asked for ordered eviction

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach to show understanding. Next, present the optimal sliding window solution with frequency map, and optionally mention the ordered dictionary approach if time permits.

How to Present

Clarify the problem and constraints with the interviewer.Describe the brute force approach to demonstrate understanding.Explain why brute force is inefficient and introduce the sliding window technique.Detail the sliding window with frequency map approach and its time complexity.Write clean, tested code for the sliding window solution.Discuss edge cases and test your code with examples.Optionally mention the ordered dictionary approach as an alternative.

Time Allocation

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

What the Interviewer Tests

The interviewer tests your ability to identify the sliding window pattern, manage frequency maps, handle edge cases, and write clean, efficient code.

Common Follow-ups

• What if k = 0? → Return 0 immediately.
• How to return the substring itself, not just length? → Track start index of max window.

💡 These follow-ups test your attention to edge cases and ability to extend the solution beyond just length calculation.

🔍

Pattern Recognition

When to Use

1) Problem asks for longest/shortest substring or subarray; 2) Constraint on distinct elements or frequency; 3) Need to find max/min length; 4) Input size large, requiring O(n) or O(n log n) solution.

Signature Phrases

'longest substring with at most k distinct characters''find the length of the longest substring containing at most k distinct characters'

NOT This Pattern When

Problems asking for substrings with exact counts or permutations often require different techniques like hashing or DP.

Similar Problems

Longest Substring Without Repeating Characters - special case where k=1Minimum Window Substring - sliding window with substring containmentLongest Substring with At Most Two Distinct Characters - k=2 special case

Practice

1. You are given a string and an integer k. You want to find the length of the longest substring where you can replace at most k characters to make all characters in that substring the same. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Brute force checking all substrings and counting character frequencies for each substring.

B. Dynamic programming that stores the longest substring ending at each index for every character.

C. Greedy approach that always replaces the first different character encountered until k replacements are used.

D. Sliding window with a frequency array tracking the count of characters and maintaining the max frequency in the current window.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the longest substring where at most k characters can be replaced to make all characters identical.

2. Step 2: Identify the optimal approach

   Sliding window with a frequency array allows tracking the count of each character in the current window and the max frequency character count. This lets us efficiently check if the window is valid (window size minus max frequency ≤ k) and adjust window size accordingly, achieving O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sliding window with frequency array is linear and optimal [OK]

Hint: Sliding window with max frequency tracking is optimal [OK]

Common Mistakes:

• Thinking brute force is efficient enough
• Assuming greedy replacement works without window adjustments
• Confusing DP for this substring problem

2. What is the time complexity of the optimal sliding window solution for counting the number of subarrays with exactly k odd numbers in an array of length n?

medium

A. O(k * n) because the window size depends on k

B. O(n^2) due to nested loops inside the sliding window

C. O(n log n) due to sorting or binary search steps

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

Solution

1. Step 1: Analyze pointer movements

   Right pointer moves from 0 to n-1 once; left pointer only moves forward when odd_count > k.

2. Step 2: Count total operations

   Each pointer moves at most n times, so total operations are O(n) + O(n) = O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sliding window two-pointer approach is linear time [OK]

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

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Confusing k factor as multiplier
• Thinking sorting is involved

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 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 characters in s1 can be reused multiple times in the substring of s2 (i.e., the substring can contain repeated characters beyond the counts in s1). Which modification to the sliding window approach correctly handles this variant?

hard

A. Remove the match count optimization and compare frequency maps at every window slide to allow repeated characters.

B. Keep the same sliding window with frequency counts and match count, but ignore counts exceeding those in s1.

C. Use a sliding window that only checks if all characters in s1 appear at least once in the window, ignoring exact counts.

D. Modify the algorithm to only check if the window contains all unique characters of s1 regardless of frequency.

Solution

1. Step 1: Understand the variant

   Allowing reuse means the substring can have more occurrences of characters than in s1. The previous match count optimization relies on exact frequency matches, which no longer applies.

2. Step 2: Identify correct approach

   To handle repeated characters beyond s1 counts, the algorithm must compare full frequency maps at each window slide, since match count optimization assumes exact matches.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Match count optimization breaks if counts can exceed s1 counts [OK]

Hint: Exact frequency match optimization fails if counts can exceed s1 [OK]

Common Mistakes:

• Assuming match count optimization still works
• Ignoring frequency counts and only checking presence