Skip to content

2107. Number of Unique Flavors After Sharing K Candies πŸ”’

Description

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

  • 0 <= candies.length <= 105
  • 1 <= candies[i] <= 105
  • 0 <= k <= candies.length

Solutions

Solution 1: Sliding Window + Hash Table

Thinking

The \(k\) shared candies form a contiguous segment; we keep the complement. Rebuilding the flavor set for every window is \(O(n)\) each and \(O(n^2)\) overall, which fails for \(n\le 10^5\).

The window length is fixed, so a shift changes the complement by one candy on each side. A frequency map of flavors outside the window has size equal to the number of unique flavors we keep.

Initialize the map with \(\textit{candies}[k:]\), slide every window of length \(k\), update both ends, and record the maximum map size.

We can maintain a sliding window of size \(k\), where the candies outside the window are for ourselves, and the \(k\) candies inside the window are shared with our sister and mother. We can use a hash table \(cnt\) to record the flavors of the candies outside the window and their corresponding quantities.

Initially, the hash table \(cnt\) stores the flavors of the candies from \(candies[k]\) to \(candies[n-1]\) and their corresponding quantities. At this time, the number of candy flavors is the size of the hash table \(cnt\), that is, \(ans = cnt.size()\).

Next, we traverse the candies in the range \([k,..n-1]\), add the current candy \(candies[i]\) to the window, and move the candy \(candies[i-k]\) on the left side of the window out of the window. Then we update the hash table \(cnt\), and update the number of candy flavors \(ans\) to \(max(ans, cnt.size())\).

After traversing all the candies, we can get the maximum number of unique flavors of candies that can be retained.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the number of candies.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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 - k]] += 1
            cnt[candies[i]] -= 1
            if cnt[candies[i]] == 0:
                cnt.pop(candies[i])
            ans = max(ans, len(cnt))
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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 < n; ++i) {
            cnt.merge(candies[i - k], 1, Integer::sum);
            if (cnt.merge(candies[i], -1, Integer::sum) == 0) {
                cnt.remove(candies[i]);
            }
            ans = Math.max(ans, cnt.size());
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int shareCandies(vector<int>& candies, int k) {
        unordered_map<int, int> cnt;
        int n = candies.size();
        for (int i = k; i < n; ++i) {
            ++cnt[candies[i]];
        }
        int ans = cnt.size();
        for (int i = k; i < n; ++i) {
            ++cnt[candies[i - k]];
            if (--cnt[candies[i]] == 0) {
                cnt.erase(candies[i]);
            }
            ans = max(ans, (int) cnt.size());
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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-k]]++
        cnt[candies[i]]--
        if cnt[candies[i]] == 0 {
            delete(cnt, candies[i])
        }
        ans = max(ans, len(cnt))
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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
    }
}

Comments