Description
Solutions
Rate-Limiting Algorithm
🔥 FULLTIME

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.

    Example 1: 

    Input:  n = 6, requests = "aaabbb", minGap = 2
    Output: 8 
    Explanation:
    


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.

    Example 2: 

    Input:  n = 12, requests = "abacadaeafag", minGap = 2
    Output: 16 
    Explanation:
    
One optimal strategy is "ab_ad_afgae_ac_a
    Constraints:
    • 1 <= length of requests <= 105
    • 0 <= minGap <= 100
    • It is guaranteed that requests contain lowercase English characters
    Thumbnail 0
    Testcase
    Result
    Case 1

    input:

    output: