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:

1
2
3
4
5
6


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:

1
2
3
4
5
6
7


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:

1
2
3
4
5
6


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

Count the frequency of each flavor in the whole array.
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.
For each window, count the number of unique flavors left (those with count > 0).
Restore the counts as the window slides.
Return the maximum number of unique flavors you can keep.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


#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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


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)

Problem#

Examples#

Solution#

Method 1 – Sliding Window and Hash Map#

Intuition#

Approach#

Code#

Complexity#