3302. Find the Lexicographically Smallest Valid Sequence

class Solution {
  public int[] validSequence(String word1, String word2) {
    int[] ans = new int[word2.length()];
    // last[j] := the index i of the last occurrence in word1, where
    // word1[i] == word2[j]
    int[] last = new int[word2.length()];
    Arrays.fill(last, -1);

    int i = word1.length() - 1;
    int j = word2.length() - 1;
    while (i >= 0 && j >= 0) {
      if (word1.charAt(i) == word2.charAt(j))
        last[j--] = i;
      --i;
    }

    boolean canSkip = true;
    j = 0;
    for (i = 0; i < word1.length(); ++i) {
      if (j == word2.length())
        break;
      if (word1.charAt(i) == word2.charAt(j)) {
        ans[j++] = i;
      } else if (canSkip && (j == word2.length() - 1 || i < last[j + 1])) {
        canSkip = false;
        ans[j++] = i;
      }
    }

    return j == word2.length() ? ans : new int[0];
  }
}

class Solution:
    def validSequence(self, word1: str, word2: str):
        m = len(word2)

        # last[j] = last possible index in word1
        # where word2[j] can be matched
        last = [-1] * m

        i = len(word1) - 1
        j = m - 1

        while i >= 0 and j >= 0:
            if word1[i] == word2[j]:
                last[j] = i
                j -= 1
            i -= 1

        ans = [0] * m

        can_skip = True
        j = 0

        for i in range(len(word1)):
            if j == m:
                break

            if word1[i] == word2[j]:
                ans[j] = i
                j += 1

            elif can_skip and (j == m - 1 or i < last[j + 1]):
                can_skip = False
                ans[j] = i
                j += 1

        return ans if j == m else []

class Solution {
public:
    vector<int> validSequence(string word1, string word2) {
        int m = word2.length();

        // last[j] = last possible index in word1
        // where word2[j] can be matched
        vector<int> last(m, -1);

        int i = word1.length() - 1;
        int j = m - 1;

        while (i >= 0 && j >= 0) {
            if (word1[i] == word2[j]) {
                last[j] = i;
                j--;
            }
            i--;
        }

        vector<int> ans(m);

        bool canSkip = true;
        j = 0;

        for (i = 0; i < word1.length(); i++) {
            if (j == m)
                break;

            if (word1[i] == word2[j]) {
                ans[j++] = i;
            }
            else if (canSkip && (j == m - 1 || i < last[j + 1])) {
                canSkip = false;
                ans[j++] = i;
            }
        }

        return j == m ? ans : vector<int>();
    }
};

class Solution {
    validSequence(word1, word2) {
        const m = word2.length;

        // last[j] = last possible index in word1
        // where word2[j] can be matched
        const last = new Array(m).fill(-1);

        let i = word1.length - 1;
        let j = m - 1;

        while (i >= 0 && j >= 0) {
            if (word1[i] === word2[j]) {
                last[j] = i;
                j--;
            }
            i--;
        }

        const ans = new Array(m);

        let canSkip = true;
        j = 0;

        for (i = 0; i < word1.length; i++) {
            if (j === m)
                break;

            if (word1[i] === word2[j]) {
                ans[j++] = i;
            } 
            else if (canSkip && (j === m - 1 || i < last[j + 1])) {
                canSkip = false;
                ans[j++] = i;
            }
        }

        return j === m ? ans : [];
    }
}