# Find the Lexicographically Smallest Valid Sequence
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-lexicographically-smallest-valid-sequence)
Canonical: https://scaleengineer.com/dsa/problems/find-the-lexicographically-smallest-valid-sequence
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
---
## Problem
You are given two strings `word1` and `word2`.

A string `x` is called **almost equal** to `y` if you can change **at most** one character in `x` to make it _identical_ to `y`.

A sequence of indices `seq` is called **valid** if:

* The indices are sorted in **ascending** order.
* _Concatenating_ the characters at these indices in `word1` in **the same** order results in a string that is **almost equal** to `word2`.

Return an array of size `word2.length` representing the lexicographically smallest **valid** sequence of indices. If no such sequence of indices exists, return an **empty** array.

**Note** that the answer must represent the _lexicographically smallest array_, **not** the corresponding string formed by those indices.

**Example 1:**

**Input:** word1 = "vbcca", word2 = "abc"

**Output:** \[0,1,2\]

**Explanation:**

The lexicographically smallest valid sequence of indices is `[0, 1, 2]`:

* Change `word1[0]` to `'a'`.
* `word1[1]` is already `'b'`.
* `word1[2]` is already `'c'`.

**Example 2:**

**Input:** word1 = "bacdc", word2 = "abc"

**Output:** \[1,2,4\]

**Explanation:**

The lexicographically smallest valid sequence of indices is `[1, 2, 4]`:

* `word1[1]` is already `'a'`.
* Change `word1[2]` to `'b'`.
* `word1[4]` is already `'c'`.

**Example 3:**

**Input:** word1 = "aaaaaa", word2 = "aaabc"

**Output:** \[\]

**Explanation:**

There is no valid sequence of indices.

**Example 4:**

**Input:** word1 = "abc", word2 = "ab"

**Output:** \[0,1\]

**Constraints:**

* `1 <= word2.length < word1.length <= 3 * 105`
* `word1` and `word2` consist only of lowercase English letters.

# Approaches
## Greedy Construction with O(m) Check
This approach builds the lexicographically smallest sequence by making a greedy choice at each position. For each element of the sequence we are trying to build, we select the smallest possible index from `word1` that can lead to a valid solution. The validity of a choice is determined by a helper function that checks if the remainder of `word2` can be formed with the available mismatches.
**Time:** O(m^2 + n*26), where m is the length of `word2` and n is the length of `word1`. The precomputation takes O(n*26). The main loop runs `m` times. Inside the loop, the `check` function is called, which takes O(m) time in the worst case. This leads to an O(m^2) complexity for the construction part. · **Space:** O(n * 26), where n is the length of `word1`. This is dominated by the precomputation tables (`nextOccurrence` and `prevOccurrence`).
**Pros:** The logic is a direct and greedy, making it relatively easy to understand.; It correctly finds the lexicographically smallest sequence if one exists.; It's more efficient than a naive backtracking approach.
**Cons:** The time complexity of O(m^2) is too slow for the given constraints, where m can be up to 3 * 10^5. This approach will likely result in a 'Time Limit Exceeded' error.
### Explanation
We construct the result array `res` of size `m` (length of `word2`) from left to right. For each index `k` from `0` to `m-1`, we want to find the smallest valid `res[k]`. A choice for `res[k]` is valid if it's possible to find the remaining elements `res[k+1], ..., res[m-1]`.

To make this efficient, we limit our search for `res[k]`. The best candidates are the first available index `j` after `res[k-1]` that either matches `word2[k]` or doesn't. Let's call them `j_match` and `j_mismatch`.

We can determine which of these candidates to pick by checking if they allow for a valid completion. This is done with a function `check(k, idx, mismatches_left)`. This function verifies if `word2[k:]` can be formed from `word1` starting after index `idx` with a certain number of mismatches. This check takes `O(m)` time. Since we do this for each of the `m` elements of the result, the total time complexity is `O(m^2)`.

Precomputation helps find candidates and perform checks faster. We use a `next_occurrence[i][char]` table to find the next index of a character, and an `R[k]` array to know the earliest starting position for a perfect suffix match of `word2[k:]`.

```java
class Solution {
    private int n, m;
    private String word1, word2;
    private int[][] nextOccurrence;
    private int[] R;

    public int[] smallestSubsequence(String w1, String w2) {
        this.word1 = w1;
        this.word2 = w2;
        this.n = word1.length();
        this.m = word2.length();

        precompute();

        int[] result = new int[m];
        int lastIdx = -1;
        int mismatchesLeft = 1;

        for (int k = 0; k < m; k++) {
            int bestNextIdx = -1;
            // Option 1: Match word2[k]
            int matchIdx = nextOccurrence[lastIdx + 1][word2.charAt(k) - 'a'];
            if (matchIdx < n && check(k + 1, matchIdx, mismatchesLeft)) {
                bestNextIdx = matchIdx;
            }

            // Option 2: Mismatch word2[k]
            if (mismatchesLeft > 0) {
                for (int c = 0; c < 26; c++) {
                    if (c == word2.charAt(k) - 'a') continue;
                    int mismatchIdx = nextOccurrence[lastIdx + 1][c];
                    if (mismatchIdx < n && (bestNextIdx == -1 || mismatchIdx < bestNextIdx)) {
                        if (check(k + 1, mismatchIdx, 0)) {
                            bestNextIdx = mismatchIdx;
                        }
                    }
                }
            }

            if (bestNextIdx == -1) {
                return new int[0]; // No solution
            }

            result[k] = bestNextIdx;
            if (word1.charAt(bestNextIdx) != word2.charAt(k)) {
                mismatchesLeft = 0;
            }
            lastIdx = bestNextIdx;
        }

        return result;
    }

    private boolean check(int k, int lastIdx, int mismatchesLeft) {
        if (k == m) return true;

        if (mismatchesLeft == 0) {
            int currentIdx = lastIdx;
            for (int i = k; i < m; i++) {
                currentIdx = nextOccurrence[currentIdx + 1][word2.charAt(i) - 'a'];
                if (currentIdx >= n) return false;
            }
            return true;
        }

        // With 1 mismatch allowed
        // Case 1: No more mismatches are used.
        if (check(k, lastIdx, 0)) return true;

        // Case 2: Use the mismatch for one of the remaining characters.
        int currentPrefixEnd = lastIdx;
        for (int p = k; p < m; p++) {
            if (p > k) {
                currentPrefixEnd = nextOccurrence[currentPrefixEnd + 1][word2.charAt(p - 1) - 'a'];
                if (currentPrefixEnd >= n) break;
            }
            if (currentPrefixEnd + 1 < R[p + 1]) {
                return true;
            }
        }
        return false;
    }

    private void precompute() {
        nextOccurrence = new int[n + 1][26];
        for (int i = 0; i < 26; i++) {
            nextOccurrence[n][i] = n;
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                nextOccurrence[i][j] = nextOccurrence[i + 1][j];
            }
            nextOccurrence[i][word1.charAt(i) - 'a'] = i;
        }

        int[][] prevOccurrence = new int[n + 1][26];
        for (int i = 0; i < 26; i++) {
            prevOccurrence[0][i] = -1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 26; j++) {
                prevOccurrence[i][j] = prevOccurrence[i - 1][j];
            }
            prevOccurrence[i][word1.charAt(i - 1) - 'a'] = i - 1;
        }

        R = new int[m + 1];
        R[m] = n;
        for (int i = m - 1; i >= 0; i--) {
            if (R[i + 1] == 0) {
                R[i] = -1;
            } else {
                R[i] = prevOccurrence[R[i + 1]][word2.charAt(i) - 'a'];
            }
        }
    }
}
```
### Algorithm
1.  **Greedy Element-by-Element Construction**: The core idea is to build the result sequence, let's call it `res`, one index at a time, from `k = 0` to `m-1`, where `m` is the length of `word2`.
2.  **Lexicographical Minimization**: At each step `k`, we aim to choose the smallest possible index `j` from `word1` for `res[k]` such that `j` is greater than the previously chosen index `res[k-1]`.
3.  **Candidate Choices**: For any step `k`, there are two primary candidates for `res[k]`:
    *   `j_match`: The smallest index `j > res[k-1]` where `word1[j] == word2[k]`.
    *   `j_mismatch`: The smallest index `j > res[k-1]` where `word1[j] != word2[k]`. A mismatch is only an option if we haven't used our single allowed mismatch yet.
4.  **Validity Check**: After picking a candidate index `j`, we must verify that it's possible to complete the rest of the sequence (`word2[k+1:]`) using indices from `word1` greater than `j` with the remaining allowed mismatches. This check is crucial.
5.  **Check Function**: A helper function, `check(k, last_idx, mismatches_left)`, is implemented. It returns `true` if `word2[k:]` can be formed from `word1` using indices greater than `last_idx` with at most `mismatches_left` changes.
    *   `check(..., 0)`: This requires a perfect match. We can verify this by greedily finding each character of `word2[k:]` in `word1` starting after `last_idx`. This takes `O(m-k)` time.
    *   `check(..., 1)`: This allows one mismatch. We can iterate through all possible mismatch positions `p` from `k` to `m-1`. For each `p`, we check if we can form a perfect match for the prefix `word2[k...p-1]` and the suffix `word2[p+1...m-1]` with a gap in between. This check also takes `O(m-k)` time.
6.  **Precomputation**: To speed up finding `j_match`, `j_mismatch`, and performing the checks, we precompute `next_occurrence` and `R` arrays. `R[k]` stores the starting index of the earliest possible perfect match for the suffix `word2[k:]`.
7.  **Main Loop**: The main algorithm iterates `k` from `0` to `m-1`. In each iteration, it evaluates `j_match` and `j_mismatch`, uses the `check` function to see which is viable, and picks the smaller of the valid candidates to append to `res`.

## Memoized Recursion
This approach refines the greedy strategy by using recursion with memoization. Instead of an iterative loop with an explicit check function, we define a recursive function that solves the problem for a suffix of `word2`. By caching the results of this function for each unique state `(k, last_idx, mismatches_left)`, we can significantly reduce redundant computations, especially if the number of distinct subproblems encountered is much smaller than the theoretical maximum. This is often the case in practice and can pass constraints where an `O(m^2)` iterative solution would fail.
**Time:** O(S * m + n*26), where S is the number of states `(k, last_idx, mismatches_left)` visited. Each state computation involves some constant work and comparing sequences, which can take O(m) time. If S is small, this is much better than O(m^2). For example, if S is O(m), the complexity would be O(m^2), but if S is O(m*log n), it would be better. The worst-case is still high, but it performs well on average. · **Space:** O(S + n*26), where S is the number of states stored in the memoization table. In the worst case, S can be O(m*n), but in practice, it's often much smaller. The `n*26` part is for precomputation.
**Pros:** Significantly more efficient than the O(m^2) approach for test cases where the number of recursive states is small.; It is the most likely approach to pass the given constraints.; The recursive structure can be a more natural way to express the greedy decision-making process.
**Cons:** The worst-case time and space complexity can still be high if the number of unique `last_idx` values encountered during recursion is large.; The implementation is more complex than the iterative approach due to recursion and memoization management.
### Explanation
The core of this method is a recursive function, let's name it `solve(k, last_idx, mismatches_left)`. This function's goal is to find and return the lexicographically smallest valid sequence for the subproblem defined by `word2`'s suffix starting at `k`, requiring all chosen indices to be greater than `last_idx`, and having `mismatches_left` available.

Inside the function, we first check our memoization table. If the result for the current state `(k, last_idx, mismatches_left)` is already computed, we return it. Otherwise, we calculate it.

The calculation involves exploring the two greedy choices:
1.  **Try to match `word2[k]`**: Find the smallest index `j_match > last_idx` where `word1[j_match] == word2[k]`. If found, we recursively call `solve(k+1, j_match, mismatches_left)`. If the recursive call returns a valid sequence, we prepend `j_match` to it to form a candidate solution.
2.  **Try to mismatch `word2[k]`**: This is only possible if `mismatches_left == 1`. We find the smallest index `j_mismatch > last_idx` where `word1[j_mismatch] != word2[k]`. If found, we recursively call `solve(k+1, j_mismatch, 0)` (since the mismatch is now used). If this returns a valid sequence, we prepend `j_mismatch` to form a second candidate.

Finally, we compare the two candidate sequences lexicographically and choose the smaller one. If only one is valid, we choose that one. If neither is valid, we mark this state as unsolvable. The result is stored in the memoization table before being returned.

Because the range of `last_idx` is large, we use hash maps for memoization: `Map<Integer, int[]>[] memo[2]`, where the first dimension is for `mismatches_left`.

```java
class Solution {
    private int n, m;
    private String word1, word2;
    private int[][] nextOccurrence;
    private int[][] nextOccurrenceNot;
    private Map<Integer, int[]>[] memo;
    private final int[] IMPOSSIBLE = new int[]{-1}; // Sentinel for impossible

    public int[] smallestSubsequence(String w1, String w2) {
        this.word1 = w1;
        this.word2 = w2;
        this.n = word1.length();
        this.m = word2.length();

        precompute();
        
        memo = new Map[2];
        memo[0] = new HashMap<>();
        memo[1] = new HashMap<>();

        int[] result = solve(0, -1, 1);
        return result == IMPOSSIBLE ? new int[0] : result;
    }

    private int[] solve(int k, int lastIdx, int mismatchesLeft) {
        if (k == m) {
            return new int[0];
        }
        if (memo[mismatchesLeft].containsKey(lastIdx * m + k)) {
            return memo[mismatchesLeft].get(lastIdx * m + k);
        }

        int[] res1 = IMPOSSIBLE;
        int matchIdx = nextOccurrence[lastIdx + 1][word2.charAt(k) - 'a'];
        if (matchIdx < n) {
            int[] suffix = solve(k + 1, matchIdx, mismatchesLeft);
            if (suffix != IMPOSSIBLE) {
                res1 = new int[1 + suffix.length];
                res1[0] = matchIdx;
                System.arraycopy(suffix, 0, res1, 1, suffix.length);
            }
        }

        int[] res2 = IMPOSSIBLE;
        if (mismatchesLeft > 0) {
            int mismatchIdx = nextOccurrenceNot[lastIdx + 1][word2.charAt(k) - 'a'];
            if (mismatchIdx < n) {
                int[] suffix = solve(k + 1, mismatchIdx, 0);
                if (suffix != IMPOSSIBLE) {
                    res2 = new int[1 + suffix.length];
                    res2[0] = mismatchIdx;
                    System.arraycopy(suffix, 0, res2, 1, suffix.length);
                }
            }
        }

        int[] result = IMPOSSIBLE;
        if (res1 != IMPOSSIBLE && res2 != IMPOSSIBLE) {
            result = isSmaller(res1, res2) ? res1 : res2;
        } else if (res1 != IMPOSSIBLE) {
            result = res1;
        } else {
            result = res2;
        }
        
        memo[mismatchesLeft].put(lastIdx * m + k, result);
        return result;
    }

    private boolean isSmaller(int[] a, int[] b) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] < b[i]) return true;
            if (a[i] > b[i]) return false;
        }
        return false;
    }

    private void precompute() {
        nextOccurrence = new int[n + 2][26];
        nextOccurrenceNot = new int[n + 2][26];
        for (int i = 0; i < 26; i++) {
            nextOccurrence[n][i] = nextOccurrence[n+1][i] = n;
            nextOccurrenceNot[n][i] = nextOccurrenceNot[n+1][i] = n;
        }

        for (int i = n - 1; i >= 0; i--) {
            int minOther = n, minOtherNot = n;
            for (int j = 0; j < 26; j++) {
                nextOccurrence[i][j] = nextOccurrence[i + 1][j];
                if (j != (word1.charAt(i) - 'a')) {
                    minOtherNot = Math.min(minOtherNot, nextOccurrence[i+1][j]);
                }
            }
            nextOccurrence[i][word1.charAt(i) - 'a'] = i;
            for (int j = 0; j < 26; j++) {
                nextOccurrenceNot[i][j] = (word1.charAt(i) - 'a' != j) ? i : minOtherNot;
            }
        }
    }
}
```
### Algorithm
1.  **Recursive Formulation**: The problem of finding the lexicographically smallest sequence can be framed recursively. We define a function, `solve(k, last_idx, mismatches_left)`, that returns the best possible sequence for `word2[k:]` using indices from `word1` greater than `last_idx`.
2.  **Greedy Choices in Recursion**: Inside `solve`, we explore the same two greedy choices as the iterative approach:
    *   **Match**: Pick the first available matching character for `word2[k]` at index `j_match`. Recursively call `solve(k+1, j_match, mismatches_left)` to get the rest of the sequence.
    *   **Mismatch**: If a mismatch is allowed (`mismatches_left == 1`), pick the first available non-matching character at index `j_mismatch`. Recursively call `solve(k+1, j_mismatch, 0)`.
3.  **Combine and Compare**: The function `solve` compares the full sequences returned by the recursive calls (e.g., `[j_match] + solve(...)` vs `[j_mismatch] + solve(...)`) and returns the lexicographically smaller one.
4.  **Memoization**: Many recursive calls will have the same state `(k, last_idx, mismatches_left)`. To avoid re-computation, we store the results of `solve` in a memoization table (a cache). When `solve` is called with a state that's already in the cache, we return the stored result immediately.
5.  **State Space**: The state is defined by `k`, `last_idx`, and `mismatches_left`. Since `last_idx` can be any index from `-1` to `n-1`, a simple 3D array for memoization is too large. Instead, we use a hash map for each `k` and `mismatches_left`, mapping `last_idx` to the computed result. `Map<Integer, int[]>[] memo`.
6.  **Initial Call**: The process starts with an initial call `solve(0, -1, 1)`.