FastPrepFastPrep
Problem Brief

Rate-Limiting Algorithm

FULLTIMEOA

Some developers at Amazon are building a prototype for a simple rate-limiting algorithm. There are n requests to be processed by the server, represented by a string requests, where the i-th character represents the region of the i-th client. Each request takes 1 unit of time to process.

There must be a minimum time gap of minGap units between any two requests from the same region.

  • The requests can be sent in any order, and there can be gaps in transmission for testing purposes.
  • Find the minimum amount of time required to process all the requests such that no request is denied.

    • Function Description

    Complete the function getMinTime in the editor.

    getMinTime has the following parameters:

    1. n: int: the number of requests
    2. requests: String: a string representing the region of each request
    3. minGap: int: the minimum time gap required between requests from the same region

    Returns

    The function should return an integer representing the minimum time required to process all requests without denial.

    1Example 1

    Input
    n = 6, requests = "aaabbb", minGap = 2
    Output
    8
    Explanation
    Example 1 illustration
    The requests can be sent in the order ab_ab_ab where _ represents that no request was sent in that unit time. Here, the minimum time gap between two requests from the same region is minGap = 2. The total time taken is 8 units.

    2Example 2

    Input
    n = 12, requests = "abacadaeafag", minGap = 2
    Output
    16
    Explanation
    One optimal strategy is "ab_ad_afgae_ac_a

    Constraints

    Limits and guarantees your solution can rely on.

  • 1 <= length of requests <= 105
  • 0 <= minGap <= 100
  • It is guaranteed that requests contain lowercase English characters
    • public int getMinTime2(int n, String requests, int minGap) {
  // write your code here
}
    Input

    n

    6

    requests

    "aaabbb"

    minGap

    2

    Output

    8

    Sign in to submit your solution.