Maximum Gap Between Stations - Video Solutions
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 involving Two Pointers, String, Greedy. 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.
Approach Overview
Problem Overview: You are given a sorted list of station positions along a route. Find the maximum distance between any two consecutive stations.
Approach 1: Brute Force (O(n log n) time, O(1) space)
If the input is not guaranteed to be sorted, sort it first. Then iterate through the sorted array once, computing the difference between each adjacent pair and tracking the maximum. This approach is straightforward and works for small inputs or when you need a quick solution without worrying about performance. The sorting step dominates the time complexity, making it O(n log n).
Approach 2: Greedy Single Pass (O(n) time, O(1) space)
When the input is already sorted, you can solve this in a single pass. Maintain a variable to store the maximum gap found so far, initialized to 0. Iterate from the second element to the end, computing stations[i] - stations[i-1] and updating the maximum if the current gap is larger. This greedy approach works because the maximum gap is simply the largest adjacent difference—no other data structure or precomputation is needed. It is optimal in both time and space.
Recommended for interviews: The greedy single-pass solution is what interviewers expect. It shows you recognize that the problem reduces to finding the maximum of adjacent differences and that you can implement it cleanly in O(n) time. Mentioning the brute force first demonstrates you understand the problem's fundamentals, but the optimal solution is what sets you apart.
This problem falls under Greedy algorithms and also touches on Arrays and Two Pointers concepts when considering variations.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force (Sort + Scan) | O(n log n) | O(1) | When input is unsorted or n is small |
| Greedy Single Pass | O(n) | O(1) | When input is already sorted or you need optimal performance |