Maximum Gap Between Stations - Solution & Explanation

Medium8 min read

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 j_i be the index of the station assigned to worker i. A valid assignment must satisfy:

station[j_i] == skill[i] for every 0 <= i < n.
The assigned station indices must be strictly increasing in worker order, meaning j₀ < j₁ < ... < j_{n - 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(j_i - j_{i - 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 station j = 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 station j = 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 == n
station.length == m
1 <= n <= m <= 10⁵
skill and station consist of lowercase English letters.
It is guaranteed that a valid assignment exists for every worker.

Solution

The maximum gap must occur between some pair of consecutive workers (i, i+1). To maximize this pair's gap, workers 0, 1, ldots, i should be assigned as far left as possible, and workers i+1, ldots, n-1 as far right as possible.

Thus, we scan from right to left and precompute suf[i]: the rightmost station worker i can take, assuming workers i+1, ldots, n-1 occupy even righter stations. Then we scan from left to right, assign worker i to the current leftmost matching station pre, and update the answer with suf[i+1] - pre.

We take the maximum over all consecutive pairs. If there is only one worker, the answer is 0.

The time complexity is O(n + m), and the space complexity is O(n), where n and m are the lengths of skill and station, respectively.