Maximum Gap Between Stations | Leetcode 4026 | Two Pointer

class Solution {
public:
    int maximumGap(string skill, string station) {
        int n = skill.size();

        //Step-1: Find the earliest valid occurence of skills
        vector<int> earliest(n);
        int pos = 0;
        for(int i=0;i<n;++i){
            while(skill[i]!=station[pos])
                pos++;
            earliest[i] = pos;
            pos++;
        }

        //Step-2: Find the latest valid occurence of skills
        vector<int> latest(n);
        pos = station.size()-1;
        for(int i=n-1;i>=0;--i){
            while(skill[i]!=station[pos])
                pos--;
            latest[i] = pos;
            pos--;
        }

        //Step-3: Compute max_gap
        int max_gap = 0;
        for(int i=0;i<n-1;++i)
            max_gap = max(max_gap,latest[i+1] - earliest[i]);
        
        return max_gap;
    }
};

/*
//JAVA
class Solution {
    public int maximumGap(String skill, String station) {
        int n = skill.length();

        // Step-1: Find the earliest valid occurrence of skills
        int[] earliest = new int[n];
        int pos = 0;

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

            earliest[i] = pos;
            pos++;
        }

        // Step-2: Find the latest valid occurrence of skills
        int[] latest = new int[n];
        pos = station.length() - 1;

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

            latest[i] = pos;
            pos--;
        }

        // Step-3: Compute max_gap
        int maxGap = 0;

        for (int i = 0; i < n - 1; i++) {
            maxGap = Math.max(maxGap, latest[i + 1] - earliest[i]);
        }

        return maxGap;
    }
}

//Python
class Solution:
    def maximumGap(self, skill: str, station: str) -> int:
        n = len(skill)

        # Step-1: Find the earliest valid occurrence of skills
        earliest = [0] * n
        pos = 0

        for i in range(n):
            while skill[i] != station[pos]:
                pos += 1

            earliest[i] = pos
            pos += 1

        # Step-2: Find the latest valid occurrence of skills
        latest = [0] * n
        pos = len(station) - 1

        for i in range(n - 1, -1, -1):
            while skill[i] != station[pos]:
                pos -= 1

            latest[i] = pos
            pos -= 1

        # Step-3: Compute max_gap
        max_gap = 0

        for i in range(n - 1):
            max_gap = max(max_gap, latest[i + 1] - earliest[i])

        return max_gap
*/