Task Scheduler With Cooldown

You are given a multiset of N tasks, each represented by an uppercase letter, and a cooldown value K: after a task of a given type runs, the same task type cannot run again until at least K time units have passed. In each time unit the CPU either executes exactly one task or sits idle. Tasks may be reordered freely. Determine the minimum total number of time units required to finish all N tasks while respecting the cooldown constraint for every task type.

Input: The first line contains two integers N and K. The second line contains a string of N uppercase letters (no spaces) representing the tasks. Output: Print a single integer: the minimum number of time units needed to complete all tasks.

1 <= N <= 100000, 0 <= K <= 100, each task is an uppercase letter 'A'-'Z'

This problem is fundamentally a GREEDY constructive-formula problem dressed up as a scheduling puzzle - recognizing that the MOST CONSTRAINED resource (the highest-frequency task) determines the overall structure is a broadly reusable scheduling-problem insight.

Schedule tasks (each needing a cooldown before repeating) to finish everything in the minimum total time, allowing idle slots when necessary. Brute force: Try every possible ordering of tasks directly and check the minimum total time each requires - this is combinatorially expensive (many possible orderings), impractical for larger task counts. Optimised: Focusing on the MOST FREQUENT task type first (since it structurally FORCES the minimum possible schedule length via its own cooldown requirement) and then greedily filling the resulting gaps with other tasks reduces this from an ordering-search problem to a straightforward formula-plus-greedy-fill calculation.

1. The task type with the HIGHEST FREQUENCY forces a minimum-length 'skeleton' of cooldown gaps built around each of its occurrences. 2. Try to fill the idle gaps in that skeleton with OTHER pending task types (any tasks that don't violate their own cooldown) before resorting to true idle slots. 3. If the TOTAL number of tasks already exceeds the skeleton's length, there's no room left for forced idling at all - the answer is simply the total task count.

Time: O(n) - counting frequencies and computing the skeleton-based formula are both linear in the number of tasks. Space: O(1) - just frequency counts for each of the 26 possible uppercase letters.

When K = 0 there is no cooldown restriction at all, so the answer is simply N; when every task is the same letter, the answer is driven entirely by the (count-1)*(K+1)+1 skeleton formula.

Be ready to derive the skeleton-length formula explicitly: (maxFrequency - 1) * (K + 1) + (number of task TYPES that share that same max frequency) - and to explain why the answer is simply the total task count whenever that count already exceeds this skeleton length.