4026. Maximum Gap Between Stations

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_0 < j_1 < ... < 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.

class Solution {
public:
    int maximumGap(string skill, string station) {
        int n = skill.size();
        if(n == 1) return 0;
        if(skill.size() == station.size()) return 1;
        vector<int> f(n), b(n);
        for(int i = 0, j = 0; i < n; j++) {
            if(skill[i] == station[j]) f[i++] = j;
        }
        for(int i = n - 1, j = station.size() - 1; i >= 0; j--) {
            if(skill[i] == station[j]) b[i--] = j;
        }
        int res = 0;
        for(int i = 0; i < n - 1; i++) {
            res = max(res, b[i+1] - f[i]);
        }
        return res;
    }
};