Find the Lexicographically Smallest Valid Sequence

Med

#2932Time: 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`).

Patterns

Two Pointers Dynamic Programming Greedy

Data structures

String

Prompt

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 * 10⁵
word1 and word2 consist only of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

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.
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].
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.
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.
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.
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:].
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.

Walkthrough

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:].

1class Solution {2    private int n, m;3    private String word1, word2;4    private int[][] nextOccurrence;5    private int[] R;6 7    public int[] smallestSubsequence(String w1, String w2) {8        this.word1 = w1;9        this.word2 = w2;10        this.n = word1.length();11        this.m = word2.length();12 13        precompute();14 15        int[] result = new int[m];16        int lastIdx = -1;17        int mismatchesLeft = 1;18 19        for (int k = 0; k < m; k++) {20            int bestNextIdx = -1;21            // Option 1: Match word2[k]22            int matchIdx = nextOccurrence[lastIdx + 1][word2.charAt(k) - 'a'];23            if (matchIdx < n && check(k + 1, matchIdx, mismatchesLeft)) {24                bestNextIdx = matchIdx;25            }26 27            // Option 2: Mismatch word2[k]28            if (mismatchesLeft > 0) {29                for (int c = 0; c < 26; c++) {30                    if (c == word2.charAt(k) - 'a') continue;31                    int mismatchIdx = nextOccurrence[lastIdx + 1][c];32                    if (mismatchIdx < n && (bestNextIdx == -1 || mismatchIdx < bestNextIdx)) {33                        if (check(k + 1, mismatchIdx, 0)) {34                            bestNextIdx = mismatchIdx;35                        }36                    }37                }38            }39 40            if (bestNextIdx == -1) {41                return new int[0]; // No solution42            }43 44            result[k] = bestNextIdx;45            if (word1.charAt(bestNextIdx) != word2.charAt(k)) {46                mismatchesLeft = 0;47            }48            lastIdx = bestNextIdx;49        }50 51        return result;52    }53 54    private boolean check(int k, int lastIdx, int mismatchesLeft) {55        if (k == m) return true;56 57        if (mismatchesLeft == 0) {58            int currentIdx = lastIdx;59            for (int i = k; i < m; i++) {60                currentIdx = nextOccurrence[currentIdx + 1][word2.charAt(i) - 'a'];61                if (currentIdx >= n) return false;62            }63            return true;64        }65 66        // With 1 mismatch allowed67        // Case 1: No more mismatches are used.68        if (check(k, lastIdx, 0)) return true;69 70        // Case 2: Use the mismatch for one of the remaining characters.71        int currentPrefixEnd = lastIdx;72        for (int p = k; p < m; p++) {73            if (p > k) {74                currentPrefixEnd = nextOccurrence[currentPrefixEnd + 1][word2.charAt(p - 1) - 'a'];75                if (currentPrefixEnd >= n) break;76            }77            if (currentPrefixEnd + 1 < R[p + 1]) {78                return true;79            }80        }81        return false;82    }83 84    private void precompute() {85        nextOccurrence = new int[n + 1][26];86        for (int i = 0; i < 26; i++) {87            nextOccurrence[n][i] = n;88        }89        for (int i = n - 1; i >= 0; i--) {90            for (int j = 0; j < 26; j++) {91                nextOccurrence[i][j] = nextOccurrence[i + 1][j];92            }93            nextOccurrence[i][word1.charAt(i) - 'a'] = i;94        }95 96        int[][] prevOccurrence = new int[n + 1][26];97        for (int i = 0; i < 26; i++) {98            prevOccurrence[0][i] = -1;99        }100        for (int i = 1; i <= n; i++) {101            for (int j = 0; j < 26; j++) {102                prevOccurrence[i][j] = prevOccurrence[i - 1][j];103            }104            prevOccurrence[i][word1.charAt(i - 1) - 'a'] = i - 1;105        }106 107        R = new int[m + 1];108        R[m] = n;109        for (int i = m - 1; i >= 0; i--) {110            if (R[i + 1] == 0) {111                R[i] = -1;112            } else {113                R[i] = prevOccurrence[R[i + 1]][word2.charAt(i) - 'a'];114            }115        }116    }117}

Complexity

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`).

Trade-offs

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.

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.

Algorithm

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.
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).
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.
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.
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.
Initial Call: The process starts with an initial call solve(0, -1, 1).

Walkthrough

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:

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.
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.

1class Solution {2    private int n, m;3    private String word1, word2;4    private int[][] nextOccurrence;5    private int[][] nextOccurrenceNot;6    private Map<Integer, int[]>[] memo;7    private final int[] IMPOSSIBLE = new int[]{-1}; // Sentinel for impossible8 9    public int[] smallestSubsequence(String w1, String w2) {10        this.word1 = w1;11        this.word2 = w2;12        this.n = word1.length();13        this.m = word2.length();14 15        precompute();16        17        memo = new Map[2];18        memo[0] = new HashMap<>();19        memo[1] = new HashMap<>();20 21        int[] result = solve(0, -1, 1);22        return result == IMPOSSIBLE ? new int[0] : result;23    }24 25    private int[] solve(int k, int lastIdx, int mismatchesLeft) {26        if (k == m) {27            return new int[0];28        }29        if (memo[mismatchesLeft].containsKey(lastIdx * m + k)) {30            return memo[mismatchesLeft].get(lastIdx * m + k);31        }32 33        int[] res1 = IMPOSSIBLE;34        int matchIdx = nextOccurrence[lastIdx + 1][word2.charAt(k) - 'a'];35        if (matchIdx < n) {36            int[] suffix = solve(k + 1, matchIdx, mismatchesLeft);37            if (suffix != IMPOSSIBLE) {38                res1 = new int[1 + suffix.length];39                res1[0] = matchIdx;40                System.arraycopy(suffix, 0, res1, 1, suffix.length);41            }42        }43 44        int[] res2 = IMPOSSIBLE;45        if (mismatchesLeft > 0) {46            int mismatchIdx = nextOccurrenceNot[lastIdx + 1][word2.charAt(k) - 'a'];47            if (mismatchIdx < n) {48                int[] suffix = solve(k + 1, mismatchIdx, 0);49                if (suffix != IMPOSSIBLE) {50                    res2 = new int[1 + suffix.length];51                    res2[0] = mismatchIdx;52                    System.arraycopy(suffix, 0, res2, 1, suffix.length);53                }54            }55        }56 57        int[] result = IMPOSSIBLE;58        if (res1 != IMPOSSIBLE && res2 != IMPOSSIBLE) {59            result = isSmaller(res1, res2) ? res1 : res2;60        } else if (res1 != IMPOSSIBLE) {61            result = res1;62        } else {63            result = res2;64        }65        66        memo[mismatchesLeft].put(lastIdx * m + k, result);67        return result;68    }69 70    private boolean isSmaller(int[] a, int[] b) {71        for (int i = 0; i < a.length; i++) {72            if (a[i] < b[i]) return true;73            if (a[i] > b[i]) return false;74        }75        return false;76    }77 78    private void precompute() {79        nextOccurrence = new int[n + 2][26];80        nextOccurrenceNot = new int[n + 2][26];81        for (int i = 0; i < 26; i++) {82            nextOccurrence[n][i] = nextOccurrence[n+1][i] = n;83            nextOccurrenceNot[n][i] = nextOccurrenceNot[n+1][i] = n;84        }85 86        for (int i = n - 1; i >= 0; i--) {87            int minOther = n, minOtherNot = n;88            for (int j = 0; j < 26; j++) {89                nextOccurrence[i][j] = nextOccurrence[i + 1][j];90                if (j != (word1.charAt(i) - 'a')) {91                    minOtherNot = Math.min(minOtherNot, nextOccurrence[i+1][j]);92                }93            }94            nextOccurrence[i][word1.charAt(i) - 'a'] = i;95            for (int j = 0; j < 26; j++) {96                nextOccurrenceNot[i][j] = (word1.charAt(i) - 'a' != j) ? i : minOtherNot;97            }98        }99    }100}

Complexity

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.

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem