Number of Unique Flavors After Sharing K Candies

Problem

You are given a 0-indexed integer array candies, where candies[i] represents the flavor of the ith candy. Your mom wants you to share these candies with your little sister by giving her k consecutive candies, but you want to keep as many flavors of candies as possible.

Return _themaximum number of unique flavors of candy you can keep after sharing _with your sister.

Examples

Example 1:

Input: candies = [1,_2,2,3_ ,4,3], k = 3
Output: 3
Explanation: 
Give the candies in the range [1, 3] (inclusive) with flavors [2,2,3].
You can eat candies with flavors [1,4,3].
There are 3 unique flavors, so return 3.

Example 2:

Input: candies = [2,2,2,_2,3_ ,3], k = 2
Output: 2
Explanation: 
Give the candies in the range [3, 4] (inclusive) with flavors [2,3].
You can eat candies with flavors [2,2,2,3].
There are 2 unique flavors, so return 2.
Note that you can also share the candies with flavors [2,2] and eat the candies with flavors [2,2,3,3].

Example 3:

Input: candies = [2,4,5], k = 0
Output: 3
Explanation: 
You do not have to give any candies.
You can eat the candies with flavors [2,4,5].
There are 3 unique flavors, so return 3.

Constraints:

• 0 <= candies.length <= 10^5
• 1 <= candies[i] <= 10^5
• 0 <= k <= candies.length

Solution

Method 1 – Sliding Window and Hash Map

Intuition

To maximize the number of unique flavors you keep, you want to minimize the number of unique flavors in the k-length window you give away. For each possible window, count the unique flavors outside the window. Use a sliding window and a hash map to efficiently track the counts.

Approach

1. Count the frequency of each flavor in the whole array.
2. Use a sliding window of size k to represent the candies given away. For each window, decrement the count of the flavors in the window.
3. For each window, count the number of unique flavors left (those with count > 0).
4. Restore the counts as the window slides.
5. Return the maximum number of unique flavors you can keep.

Code

C++

#include <unordered_map>
class Solution {
public:
    int shareCandies(vector<int>& candies, int k) {
        unordered_map<int, int> freq;
        for (int c : candies) freq[c]++;
        int n = candies.size(), ans = 0;
        unordered_map<int, int> window;
        for (int i = 0; i < k; ++i) window[candies[i]]++;
        for (int i = 0; i <= n - k; ++i) {
            for (auto& [f, cnt] : window) freq[f] -= cnt;
            int cur = 0;
            for (auto& [f, cnt] : freq) if (cnt > 0) cur++;
            ans = max(ans, cur);
            for (auto& [f, cnt] : window) freq[f] += cnt;
            if (i + k < n) {
                window[candies[i]]--;
                if (window[candies[i]] == 0) window.erase(candies[i]);
                window[candies[i + k]]++;
            }
        }
        return ans;
    }
};

Go

func shareCandies(candies []int, k int) int {
    freq := map[int]int{}
    for _, c := range candies { freq[c]++ }
    n, ans := len(candies), 0
    window := map[int]int{}
    for i := 0; i < k; i++ { window[candies[i]]++ }
    for i := 0; i <= n-k; i++ {
        for f, cnt := range window { freq[f] -= cnt }
        cur := 0
        for _, cnt := range freq { if cnt > 0 { cur++ } }
        if cur > ans { ans = cur }
        for f, cnt := range window { freq[f] += cnt }
        if i+k < n {
            window[candies[i]]--
            if window[candies[i]] == 0 { delete(window, candies[i]) }
            window[candies[i+k]]++
        }
    }
    return ans
}

Java

import java.util.*;
class Solution {
    public int shareCandies(int[] candies, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int c : candies) freq.put(c, freq.getOrDefault(c, 0) + 1);
        int n = candies.length, ans = 0;
        Map<Integer, Integer> window = new HashMap<>();
        for (int i = 0; i < k; i++) window.put(candies[i], window.getOrDefault(candies[i], 0) + 1);
        for (int i = 0; i <= n - k; i++) {
            for (Map.Entry<Integer, Integer> e : window.entrySet()) freq.put(e.getKey(), freq.get(e.getKey()) - e.getValue());
            int cur = 0;
            for (int v : freq.values()) if (v > 0) cur++;
            ans = Math.max(ans, cur);
            for (Map.Entry<Integer, Integer> e : window.entrySet()) freq.put(e.getKey(), freq.get(e.getKey()) + e.getValue());
            if (i + k < n) {
                window.put(candies[i], window.get(candies[i]) - 1);
                if (window.get(candies[i]) == 0) window.remove(candies[i]);
                window.put(candies[i + k], window.getOrDefault(candies[i + k], 0) + 1);
            }
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun shareCandies(candies: IntArray, k: Int): Int {
        val freq = mutableMapOf<Int, Int>()
        for (c in candies) freq[c] = freq.getOrDefault(c, 0) + 1
        val n = candies.size
        var ans = 0
        val window = mutableMapOf<Int, Int>()
        for (i in 0 until k) window[candies[i]] = window.getOrDefault(candies[i], 0) + 1
        for (i in 0..n - k) {
            for ((f, cnt) in window) freq[f] = freq[f]!! - cnt
            val cur = freq.values.count { it > 0 }
            ans = maxOf(ans, cur)
            for ((f, cnt) in window) freq[f] = freq[f]!! + cnt
            if (i + k < n) {
                window[candies[i]] = window[candies[i]]!! - 1
                if (window[candies[i]] == 0) window.remove(candies[i])
                window[candies[i + k]] = window.getOrDefault(candies[i + k], 0) + 1
            }
        }
        return ans
    }
}

Python

class Solution:
    def shareCandies(self, candies: list[int], k: int) -> int:
        from collections import Counter
        freq = Counter(candies)
        n = len(candies)
        ans = 0
        window = Counter(candies[:k])
        for i in range(n - k + 1):
            for f in window: freq[f] -= window[f]
            cur = sum(1 for v in freq.values() if v > 0)
            ans = max(ans, cur)
            for f in window: freq[f] += window[f]
            if i + k < n:
                window[candies[i]] -= 1
                if window[candies[i]] == 0: del window[candies[i]]
                window[candies[i + k]] += 1
        return ans

Rust

use std::collections::HashMap;
impl Solution {
    pub fn share_candies(candies: Vec<i32>, k: i32) -> i32 {
        let mut freq = HashMap::new();
        for &c in &candies { *freq.entry(c).or_insert(0) += 1; }
        let n = candies.len();
        let mut ans = 0;
        let mut window = HashMap::new();
        for i in 0..k as usize { *window.entry(candies[i]).or_insert(0) += 1; }
        for i in 0..=n - k as usize {
            for (&f, &cnt) in &window { *freq.get_mut(&f).unwrap() -= cnt; }
            let cur = freq.values().filter(|&&v| v > 0).count();
            ans = ans.max(cur);
            for (&f, &cnt) in &window { *freq.get_mut(&f).unwrap() += cnt; }
            if i + k as usize < n {
                *window.get_mut(&candies[i]).unwrap() -= 1;
                if window[&candies[i]] == 0 { window.remove(&candies[i]); }
                *window.entry(candies[i + k as usize]).or_insert(0) += 1;
            }
        }
        ans as i32
    }
}

TypeScript

class Solution {
    shareCandies(candies: number[], k: number): number {
        const freq = new Map<number, number>()
        for (const c of candies) freq.set(c, (freq.get(c) ?? 0) + 1)
        const n = candies.length
        let ans = 0
        const window = new Map<number, number>()
        for (let i = 0; i < k; i++) window.set(candies[i], (window.get(candies[i]) ?? 0) + 1)
        for (let i = 0; i <= n - k; i++) {
            for (const [f, cnt] of window) freq.set(f, freq.get(f)! - cnt)
            let cur = 0
            for (const v of freq.values()) if (v > 0) cur++
            ans = Math.max(ans, cur)
            for (const [f, cnt] of window) freq.set(f, freq.get(f)! + cnt)
            if (i + k < n) {
                window.set(candies[i], window.get(candies[i])! - 1)
                if (window.get(candies[i]) === 0) window.delete(candies[i])
                window.set(candies[i + k], (window.get(candies[i + k]) ?? 0) + 1)
            }
        }
        return ans
    }
}

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(n)