Skip to content

4026. Maximum Gap Between Stations

Description

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 every 0 <= 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 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 <= 105
  • skill and station consist of lowercase English letters.
  • It is guaranteed that a valid assignment exists for every worker.

Solutions

Solution 1: Greedy

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 \(\textit{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 \(\textit{pre}\), and update the answer with \(\textit{suf}[i+1] - \textit{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 \(\textit{skill}\) and \(\textit{station}\), respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def maximumGap(self, skill: str, station: str) -> int:
        n, m = len(skill), len(station)
        suf = [0] * n
        j = m - 1
        for i in range(n - 1, 0, -1):
            while station[j] != skill[i]:
                j -= 1
            suf[i] = j
            j -= 1

        ans = pre = 0
        for i in range(n - 1):
            while station[pre] != skill[i]:
                pre += 1
            ans = max(ans, suf[i + 1] - pre)
            pre += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int maximumGap(String skill, String station) {
        int n = skill.length();
        int m = station.length();

        int[] suf = new int[n];
        int j = m - 1;

        for (int i = n - 1; i > 0; i--) {
            while (station.charAt(j) != skill.charAt(i)) {
                j--;
            }

            suf[i] = j;
            j--;
        }

        int ans = 0;
        int pre = 0;

        for (int i = 0; i < n - 1; i++) {
            while (station.charAt(pre) != skill.charAt(i)) {
                pre++;
            }

            ans = Math.max(ans, suf[i + 1] - pre);
            pre++;
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int maximumGap(string skill, string station) {
        int n = skill.size();
        int m = station.size();

        vector<int> suf(n);
        int j = m - 1;

        for (int i = n - 1; i > 0; i--) {
            while (station[j] != skill[i]) {
                j--;
            }

            suf[i] = j;
            j--;
        }

        int ans = 0;
        int pre = 0;

        for (int i = 0; i < n - 1; i++) {
            while (station[pre] != skill[i]) {
                pre++;
            }

            ans = max(ans, suf[i + 1] - pre);
            pre++;
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
func maximumGap(skill string, station string) int {
    n, m := len(skill), len(station)

    suf := make([]int, n)
    j := m - 1

    for i := n - 1; i > 0; i-- {
        for station[j] != skill[i] {
            j--
        }

        suf[i] = j
        j--
    }

    ans := 0
    pre := 0

    for i := 0; i < n-1; i++ {
        for station[pre] != skill[i] {
            pre++
        }

        ans = max(ans, suf[i+1]-pre)

        pre++
    }

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function maximumGap(skill: string, station: string): number {
    const n = skill.length;
    const m = station.length;

    const suf: number[] = Array(n).fill(0);
    let j = m - 1;

    for (let i = n - 1; i > 0; i--) {
        while (station[j] !== skill[i]) {
            j--;
        }

        suf[i] = j;
        j--;
    }

    let ans = 0;
    let pre = 0;

    for (let i = 0; i < n - 1; i++) {
        while (station[pre] !== skill[i]) {
            pre++;
        }

        ans = Math.max(ans, suf[i + 1] - pre);
        pre++;
    }

    return ans;
}

Comments