Formatted question description: https://leetcode.ca/all/2107.html

You are given a 0-indexed integer array candies, where candies[i] represents the flavor of the i^th 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 the maximum number of unique flavors of candy you can keep after sharing with your sister.

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:

1 <= candies.length <= 10⁵
1 <= candies[i] <= 10⁵
0 <= k <= candies.length

Companies:
Microsoft

Related Topics:
Array, Hash Table, Sliding Window

Similar Questions:

Solution 1. Fixed-length Sliding Window

// OJ: https://leetcode.com/problems/number-of-unique-flavors-after-sharing-k-candies/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int shareCandies(vector<int>& A, int k) {
        unordered_map<int, int> cnt;
        int ans = 0;
        for (int n : A) cnt[n]++;
        for (int i = 0, N = A.size(); i < N; ++i) { // Give out candies in window `[i-k+1, i]`
            cnt[A[i]]--; // Give out `A[i]`
            if (i - k >= 0) cnt[A[i - k]]++; // Reclaim `A[i-k]`
            if (cnt[A[i]] == 0) cnt.erase(A[i]);
            if (i >= k - 1) ans = max(ans, (int)cnt.size()); // Take the maximum possible unique flavors left after giving out.
        }
        return ans;
    }
};

class Solution {
    public int shareCandies(int[] candies, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int n = candies.length;
        for (int i = k; i < n; ++i) {
            cnt.merge(candies[i], 1, Integer::sum);
        }
        int ans = cnt.size();
        for (int i = k; i < candies.length; ++i) {
            if (cnt.merge(candies[i], -1, Integer::sum) == 0) {
                cnt.remove(candies[i]);
            }
            cnt.merge(candies[i - k], 1, Integer::sum);
            ans = Math.max(ans, cnt.size());
        }
        return ans;
    }
}

class Solution:
    def shareCandies(self, candies: List[int], k: int) -> int:
        cnt = Counter(candies[k:])
        ans = len(cnt)
        for i in range(k, len(candies)):
            cnt[candies[i]] -= 1
            cnt[candies[i - k]] += 1
            if cnt[candies[i]] == 0:
                cnt.pop(candies[i])
            ans = max(ans, len(cnt))
        return ans

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

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

function shareCandies(candies: number[], k: number): number {
    const cnt: Map<number, number> = new Map();
    for (const x of candies.slice(k)) {
        cnt.set(x, (cnt.get(x) || 0) + 1);
    }
    let ans = cnt.size;
    for (let i = k; i < candies.length; ++i) {
        cnt.set(candies[i - k], (cnt.get(candies[i - k]) || 0) + 1);
        cnt.set(candies[i], (cnt.get(candies[i]) || 0) - 1);
        if (cnt.get(candies[i]) === 0) {
            cnt.delete(candies[i]);
        }
        ans = Math.max(ans, cnt.size);
    }
    return ans;
}

use std::collections::HashMap;

impl Solution {
    pub fn share_candies(candies: Vec<i32>, k: i32) -> i32 {
        let mut cnt = HashMap::new();
        let n = candies.len();

        for i in k as usize..n {
            *cnt.entry(candies[i]).or_insert(0) += 1;
        }

        let mut ans = cnt.len() as i32;

        for i in k as usize..n {
            *cnt.entry(candies[i - k as usize]).or_insert(0) += 1;
            if let Some(x) = cnt.get_mut(&candies[i]) {
                *x -= 1;
                if *x == 0 {
                    cnt.remove(&candies[i]);
                }
            }

            ans = ans.max(cnt.len() as i32);
        }

        ans
    }
}

Discuss

https://leetcode.com/problems/number-of-unique-flavors-after-sharing-k-candies/discuss/1658450/C%2B%2B-Fixed-length-Sliding-Window

2107 - Number of Unique Flavors After Sharing K Candies

Solution 1. Fixed-length Sliding Window

Discuss

All Problems

All Solutions

Welcome to Subscribe On Youtube

2107. Number of Unique Flavors After Sharing K Candies (Medium)

Solution 1. Fixed-length Sliding Window

Discuss

All Problems

All Solutions