You are given two strings, word1 and word2.

A sequence of indices seq is considered valid if:

• The length of seq is equal to the length of word2.

• The indices are strictly increasing, satisfying $0 \leq$ seq[0] $<$ seq[1] $< \dots <$ seq[word2.length $- 1]$ $<$ word1.length.

• The string formed by concatenating word1[seq[0]], word1[seq[1]], …, word1[seq[word2.length $- 1]]$ is almost equal to word2.

Two strings $a$ and $b$ of equal length are almost equal if they differ at at most $1$ index.

Return an array representing the lexicographically smallest valid sequence of indices. If no valid sequence exists, return an empty array.

Note: An array a is lexicographically smaller than an array b if at the first index where they differ, the element in a is strictly less than the element in b.

Constraints:

• $1 \leq$ word2.length $\leq$ word1.length $\leq 3 imes 10^5$

• word1 and word2 consist only of lowercase English letters.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.