Welcome to Subscribe On Youtube

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

Thinking

The maximum gap can only lie between some adjacent pair of workers. To widen $(i,i+1)$, workers $0..i$ should take the leftmost feasible stations and workers $i+1..n-1$ the rightmost, subject to skill matching.

A right-to-left pass stores the rightmost station worker $i$ can take once later workers have claimed righter stations; a left-to-right pass then seats worker $i$ at the leftmost match and updates the answer by the difference.

A single worker has no gap, so the answer is $0$.

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.

  • 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;
    }
}

  • 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;
    }
};

  • 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


  • 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
}


  • 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;
}

All Problems

All Solutions