Show problems as
Classic problem #4026MediumTwo PointersStringGreedy

Maximum Gap Between Stations

Real-world version: Widest Step Between Assigned Benches
Tracked in this browser only
Read Maximum Gap Between Stations on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Workers are lined up in the order given by skill, one letter each, and benches are lined up in the order given by station, one letter each. There are at least as many benches as workers.

Each worker is put on a bench whose letter matches their own, one worker per bench, and the workers keep their order: an earlier worker must take an earlier bench. At least one such assignment is guaranteed to exist.

The step between two neighbouring workers is the difference between their bench positions. Return the widest step any assignment can have, or 0 when there is only one worker.

Examples

Example 1

Input
skill = "ab", station = "aabb"
Output
3

The worker wanting an a can take bench 0 and the one wanting a b can take bench 3, which is as far apart as they go.

Example 2

Input
skill = "a", station = "a"
Output
0

With a single worker there is no neighbouring pair to measure.

Example 3

Input
skill = "ab", station = "ab"
Output
1

Each worker has exactly one bench that matches, so the step is fixed at one.

Constraints

  • 1 <= skill.length <= station.length <= 10^5
  • skill and station consist of lowercase English letters only
  • At least one assignment exists

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def maximum_gap(skill: str, station: str) -> int:
Java
public int maximumGap(String skill, String station)

More on the same topics