3302. Find the Lexicographically Smallest Valid Sequence

String
Greedy
Two Pointers
Suffix

TIME

O(n)

SPACE

O(n)

Intuition

We match word2 against a subsequence of word1, allowing at most one mismatch (the single change), and want the lexicographically smallest index array. Two facts drive the greedy:

Exact matches are free, they never consume the change, so grabbing the smallest available exact-match index for each word2[j] is always safe.
Spend the change as early as it stays feasible. At the current output position j, using the change on a mismatch gives that position a smaller index than waiting for a later exact match. A smaller value at the current output position dominates lexicographically, no matter what happens afterward, as long as the remainder can still be completed.

Feasibility of "the rest matches exactly" is answered by a suffix precomputation.

Approach

Suffix array f: f[i] = the number of trailing characters of word2 that can be matched exactly as a subsequence of word1[i:]. Compute right to left: walking i from n-1 down, advance a counter k whenever word1[i] == word2[m-1-k]; set f[i] = k.
Greedy sweep with pointers i (word1), j (word2), and a changed flag:
- If word1[i] == word2[j]: take it (exact) → append i, advance both.
- Else if the change is unused and f[i+1] >= m-j-1 (the remaining word2[j+1:] still fits exactly in word1[i+1:]): spend the change here → append i, advance both, set changed.
- Else: skip i.
If j reached m, return the collected indices; otherwise return [].

Complexity

Time: O(n), one suffix pass and one forward sweep
Space: O(n), the f array (plus the output)

Edge Cases

No valid sequence (needed character never appears, even with one change) → [] (Example 3)
Change used to shrink the first index (Example 1) → spend at position 0
word2 matches exactly with no change needed → still smallest greedy indices
word2 shorter than word1 by more than the used indices → extra word1 chars ignored
The change may be spent anywhere; the greedy places it at the earliest feasible mismatch

Code

from typing import List


class Solution:
    def validSequence(self, word1: str, word2: str) -> List[int]:
        """
        3302. Find the Lexicographically Smallest Valid Sequence
        Time: O(n)
        Space: O(n)
        """
        n, m = len(word1), len(word2)

        # f[i] = # of trailing chars of word2 matchable exactly by word1[i:]
        f = [0] * (n + 1)
        k = 0
        for i in range(n - 1, -1, -1):
            if k < m and word1[i] == word2[m - 1 - k]:
                k += 1
            f[i] = k

        res = []
        j = 0
        changed = False
        i = 0
        while i < n and j < m:
            if word1[i] == word2[j]:
                res.append(i)
                j += 1
                i += 1
            elif not changed and f[i + 1] >= m - j - 1:
                # spend the single change here; the rest still matches exactly
                res.append(i)
                j += 1
                i += 1
                changed = True
            else:
                i += 1

        return res if j == m else []

/**
 * 3302. Find the Lexicographically Smallest Valid Sequence
 * Time: O(n)
 * Space: O(n)
 */
class Solution {
    public int[] validSequence(String word1, String word2) {
        int n = word1.length(), m = word2.length();

        // f[i] = # of trailing chars of word2 matchable exactly by word1[i:]
        int[] f = new int[n + 1];
        int k = 0;
        for (int i = n - 1; i >= 0; i--) {
            if (k < m && word1.charAt(i) == word2.charAt(m - 1 - k)) {
                k++;
            }
            f[i] = k;
        }

        int[] res = new int[m];
        int j = 0, i = 0;
        boolean changed = false;
        while (i < n && j < m) {
            if (word1.charAt(i) == word2.charAt(j)) {
                res[j++] = i;
                i++;
            } else if (!changed && f[i + 1] >= m - j - 1) {
                // spend the single change here; the rest still matches exactly
                res[j++] = i;
                i++;
                changed = true;
            } else {
                i++;
            }
        }

        return j == m ? res : new int[0];
    }
}