Dsa
Sliding Window
Medium
Variety-Weighted Budget
A grocery store offers a 'custom bundle'. The total cost of a bundle is the sum of the prices of all items plus a 'diversity tax' calculated as (number of unique items in the bundle) * M. Given a list of item prices and a total budget B, find the maximum number of items you can include in a contiguous subsegment bundle.
Input Format:
- The first line contains two integers: B (total budget) and M (multiplier for unique items).
- The second line contains a space-separated list of item prices.
Output Format:
- A single integer representing the maximum window length.
Example:
Input:
15 2
3 3 4 1 5
Output:
4
(Explanation: Window [3, 3, 4, 1] has sum 11. Unique items are {3, 4, 1}, count=3. Cost = 11 + (3 * 2) = 17. Too high. Window [3, 4, 1] cost = 8 + (3 * 2) = 14. Length 3. Wait, [4, 1, 5] cost = 10 + 6 = 16. Shortest is [3, 3, 4, 1] check? No. Let's try [3, 3, 4, 1]... let's try [4, 1]... max length is 3.)
Key concepts
sliding_windowhash_map
Practise this out loud — free
Start a mock interview on THIS exact question — a voice AI interviewer opens with it, pushes back like a real onsite, then hands you an instant scorecard.
🎙 Practise this question now