Leetcode 4026 | Maximum Gap Between Stations | Leetcode weekly contest 515 | Greedy
Maximum Gap Between Stations - Video Solution
Watch 4 video solutions for Maximum Gap Between Stations, a medium level problem. This walkthrough by CodeWithMeGuys has 193 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given two strings skill and station of lengths n and m, respectively.
skill[i] represents the skill of worker i, and station[j] represents the skill supported by station j.
You must assign every worker to a distinct station. Let ji be the index of the station assigned to worker i. A valid assignment must satisfy:
station[ji] == skill[i]for every0 <= i < n.- The assigned station indices must be strictly increasing in worker order, meaning
j0 < j1 < ... < jn - 1.
The gap of an assignment is the maximum difference between the station indices assigned to two consecutive workers. In other words, it is max(ji - ji - 1) over all 1 <= i < n.
If there is only one worker, the gap is 0.
Return the maximum possible gap among all valid assignments. It is guaranteed that at least one valid assignment exists.
Example 1:
Input: skill = "aa", station = "aaaa"
Output: 3
Explanation:
- The two workers must be assigned to two different
'a'stations. - Assigning them to stations
[0, 3]gives a gap of 3.
Example 2:
Input: skill = "xyz", station = "xyzz"
Output: 2
Explanation:
- Assign worker 0 to station
j = 0, and worker 1 to stationj = 1. - To maximize the gap, assign worker 2 to station
j = 3. - This gives the assignment
[0, 1, 3]with gaps[1, 2], so the gap is 2.
Example 3:
Input: skill = "cbc", station = "cbcdbc"
Output: 4
Explanation:
- Assign worker 0 to station
j = 0, and worker 1 to stationj = 1. - To maximize the gap, assign worker 2 to station
j = 5. - This gives the assignment
[0, 1, 5]with gaps[1, 4], so the gap is 4.
Constraints:
skill.length == nstation.length == m1 <= n <= m <= 105skillandstationconsist of lowercase English letters.- It is guaranteed that a valid assignment exists for every worker.