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:
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]:
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'.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 * 105word1 and word2 consist only of lowercase English letters.In #3302 Find the Lexicographically Smallest Valid Sequence, the goal is to construct the smallest possible sequence in lexicographical order while still satisfying the problem’s validity constraints. A common strategy combines greedy decisions with two-pointer traversal and feasibility checks.
Start by scanning the strings with two pointers to determine which characters can be chosen while preserving the ability to complete the sequence. At each step, greedily prefer the smallest lexicographic character, but ensure that selecting it does not prevent forming a valid sequence later. To guarantee this, dynamic programming or suffix feasibility checks can be used to track whether the remaining characters can still satisfy the constraints.
The key idea is balancing lexicographic minimization with future feasibility. Efficient implementations precompute helpful information (such as next valid indices or suffix matches) to avoid repeated scanning. With careful pointer movement and greedy selection, the solution can be implemented in near-linear time relative to the string length.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with Two Pointers | O(n) | O(1) |
| Greedy + Dynamic Programming Feasibility Check | O(n) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Let <code>dp[i]</code> be the longest suffix of <code>word2</code> that exists as a subsequence of suffix of the substring of <code>word1</code> starting at index <code>i</code>.
If <code>dp[i + 1] < m</code> and <code>word1[i] == word2[m - dp[i + 1] - 1]</code>,<code>dp[i] = dp[i + 1] + 1</code>. Otherwise, <code>dp[i] = dp[i + 1]</code>.
For each index <code>i</code>, greedily select characters using the <code>dp</code> array to know whether a solution exists.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Greedy works well because the objective is lexicographic minimization. By always attempting to select the smallest possible character and verifying future feasibility, the algorithm ensures the resulting sequence is the smallest valid one.
Problems involving lexicographic ordering combined with greedy and dynamic programming ideas are common in technical interviews. Variants of this pattern appear in coding interviews at major tech companies because they test reasoning about optimal choices and future constraints.
Most solutions rely on arrays, pointers, and sometimes auxiliary DP arrays or precomputed index tables. These structures allow efficient tracking of remaining characters and quick validation that a choice will still allow completion of the sequence.
The optimal approach typically combines a greedy strategy with two-pointer traversal. At each step, you choose the smallest possible character while ensuring that the remaining portion of the sequence can still be completed. Feasibility checks using precomputed information or dynamic programming help guarantee correctness.