The hash map tracks the count of each fruit type in the current window. When a fruit type is removed (due to shrinking the window), its count is decremented, and it is removed from the hash map if the count reaches zero.

","question":"How is the hash map used to manage the sliding window?"}],"interview_followup_questions":[{"answer":"

Generalize the sliding window approach to handle k baskets by ensuring the hash map contains at most k fruit types at any time. The rest of the logic remains the same.

","question":"How would you modify the solution if the number of baskets increased?"},{"answer":"

Along with tracking the maximum size, store the indices of the start and end of the window whenever the maximum is updated. Return these indices.

","question":"What if you wanted to return the range of trees contributing to the maximum fruits?"}]},"problem_type":"DSA","hasIDE":true},{"problem_id":"slidingwindow/2pointer_slidingwindow/2pointer_longestandsmallestwindowproblems_longestsubstringwithatmostkdistinctcharacters","problem_name":"Longest Substring With At Most K Distinct Characters","problem_rank":4,"problem_slug":"longest-substring-with-at-most-k-distinct-characters","misc":{"tags":["Amazon","Meta","Microsoft","Oracle","Yandex","Google","Tiktok","Coupang","Goldman Sachs","AppDynamics","Bitgo"],"facts":"Fun Fact: The core concept of this problem is used in text and data analysis software. For example, in social media applications, analyzing the length of the longest substring with at most k distinct characters could help detect, track, or summarize major trends/topic, spam posts or even potential security breaches. Similarly, in bioinformatics, this idea could be applicable in DNA sequencing, where the longest substring of a DNA fragment with distinct kinds of nucleotides is important.","hints":[{"hint":"Use the two-pointer/sliding window technique with a hashmap to track character frequencies. Expand the window by adding characters until the count of distinct characters exceeds k. Shrink the window from the left until the distinct character count is at most k."},{"hint":"Instead of storing just counts, track the last occurrence of each character in an ordered dictionary. When the distinct count exceeds k, remove the leftmost character based on its last occurrence."}],"language":["cpp","java","python","javascript","csharp","go"],"topicTags":["Hash Table","Sliding Window","String"],"difficulty":"Hard","similarProblems":[{"name":"Longest Substring with At Most Two Distinct Characters","slug":"/longest-substring-with-at-most-two-distinct-characters","isPaid":true},{"name":"Longest Substring Without Repeating Characters","slug":"/longest-substring-without-repeating-characters","isPaid":false}],"frequently_occuring_doubts":[{"answer":"We need a contiguous substring, and the sliding window dynamically expands and shrinks based on the number of distinct characters.\nSince each character is added once and removed once, the approach runs in O(n) time complexity.","question":"Why does the sliding window approach work for this problem?"},{"answer":"If s is empty, return 0.\nIf k = 0, no valid substring exists, return 0.\nIf k = 1, find the longest contiguous sequence of the most frequent character.","question":"How do we handle edge cases like s = \"\", k = 0, or k = 1?"}],"interview_followup_questions":[{"answer":"Brute Force Approach: Generate all substrings and count distinct characters (O(n²) or O(n³)).\nBinary Search on Length: Check if a substring of a given length can exist with at most k distinct characters (O(n log n)).","question":"Can this problem be solved using a different approach apart from sliding window?"},{"answer":"Track the start index and end index of the longest valid window.\nInstead of returning just the length, return s[start:end+1].","question":"What if we are asked to return the substring itself instead of just the length?"}]},"problem_type":"DSA","hasIDE":true},{"problem_id":"slidingwindow/2pointer_slidingwindow/2pointer_longestandsmallestwindowproblems_longestrepeatingcharacterreplacemen