Find the Lexicographically Smallest Valid Sequence - Solution & Explanation

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.