Watch 6 video solutions for Find the Lexicographically Smallest Valid Sequence, a medium level problem involving Two Pointers, String, Dynamic Programming. This walkthrough by CodeFod has 2,214 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: You are given two strings and must return a sequence of indices from the first string that forms the second string while keeping the sequence lexicographically smallest. The challenge is not just finding a valid subsequence, but ensuring the earliest possible indices are chosen while still allowing the rest of the pattern to be completed.
Approach 1: Two-Pointer with Backtracking (O(n + m) average, O(m) space)
This approach scans the source string using two pointers. One pointer iterates through the main string while the other tracks progress through the target pattern. When characters match, record the index and advance both pointers. If a later mismatch would prevent completing the pattern, backtracking allows adjusting previously chosen indices to keep the sequence valid while maintaining lexicographic minimality. The key insight is that greedy forward matching works most of the time, while minimal backtracking corrects early decisions when the suffix cannot be formed. This technique relies heavily on two pointers and efficient string traversal.
Approach 2: Greedy with Sorting on Indices (O(n log n) time, O(n) space)
The greedy approach precomputes candidate positions for each character of the pattern inside the source string. These indices are collected and processed so that the smallest feasible index is always chosen first. Sorting candidate positions ensures lexicographic ordering, while validation checks confirm that enough characters remain to finish the sequence. The main idea is that choosing the earliest valid index preserves lexicographic order as long as the remaining suffix is still achievable. This strategy combines greedy decision making with structured index management.
Approach 3: Dynamic Programming Feasibility Check (O(n * m) time, O(m) space)
A dynamic programming helper can verify whether the remaining suffix of the pattern can still be matched after selecting a candidate index. The DP state tracks how many characters of the pattern can be matched from a given suffix of the main string. During greedy selection, this feasibility check prevents picking an index that would block completion of the sequence. Although slower than the pointer-based approach, it provides a clear correctness guarantee and demonstrates the relationship between subsequence matching and dynamic programming.
Recommended for interviews: The two-pointer greedy strategy is usually what interviewers expect. It shows you understand subsequence construction, lexicographic ordering, and how to maintain feasibility while scanning a string once. Mentioning the DP feasibility idea demonstrates deeper reasoning, but implementing the optimized two-pointer solution proves stronger algorithmic skill.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer with Backtracking | O(n + m) average | O(m) | Best general solution for subsequence matching while preserving lexicographic order |
| Greedy with Sorting on Indices | O(n log n) | O(n) | Useful when candidate indices for each character are precomputed |
| Dynamic Programming Feasibility Check | O(n * m) | O(m) | Good for understanding subsequence feasibility or verifying greedy choices |