Find the Lexicographically Smallest Valid Sequence

Find the Lexicographically Smallest Valid Sequence

What is this problem about?

In the Find the Lexicographically Smallest Valid Sequence coding problem, you are given two strings, word1 and word2. A sequence of indices from word1 is considered valid if it forms a subsequence that matches word2 with at most one character difference. Your goal is to find the lexicographically smallest sequence of such indices. If no such sequence exists, return an empty array.

Why is this asked in interviews?

This "Medium" to "Hard" problem is asked by companies like Bloomberg to evaluate a candidate's ability to handle greedy choices with look-ahead constraints. It tests your mastery of the Two Pointers interview pattern and your understanding of how to use preprocessing to make optimal decisions at each step. To find the lexicographically smallest index sequence, you want to pick the smallest possible index for each character of word2 while ensuring that the rest of word2 can still be completed.

Algorithmic pattern used

This problem uses Greedy matching with Preprocessing.

1. Preprocessing: Create a suffix array where suffix[i] stores the length of the longest suffix of word2 that can be formed using characters from word1 starting from index i.
2. Greedy Construction: Iterate through word1 and word2 using two pointers.
3. For the current character of word2, try to match it with the earliest possible index in word1.
4. If the characters match, great. If they don't, you consider using your "one allowed change."
5. You only commit to a change if the remaining part of word2 can still be formed as a subsequence from the remaining part of word1 (verified using your suffix array).

Example explanation

word1 = "abacaba", word2 = "aac"

1. Suffix array tells us how much of "aac" can be made from various starting points in "abacaba".
2. Try to match word2[0] ('a'): matches word1[0]. Index 0 is picked.
3. Try to match word2[1] ('a'): word1[1] is 'b'. Should we use our change?
   • If we change 'b' to 'a', can we finish "c" from word1[2...6]?
   • Suffix array says yes. Pick index 1 and use the change.
4. Try to match word2[2] ('c'): matches word1[3]. Pick index 3. Result: [0, 1, 3].

Common mistakes candidates make

• Pure Greedy: Trying to match without checking the suffix, which might leave you unable to complete the subsequence later.
• Inefficient checking: Re-scanning word1 for every character, resulting in $O(N imes M)$ instead of $O(N)$.
• Lexicographical confusion: Confusing the lexicographical order of the characters with the lexicographical order of the indices.

Interview preparation tip

When you need to find the "lexicographically smallest" anything, the greedy approach is usually: "Pick the smallest possible value for the first position, then the second, and so on." The hard part is ensuring that a valid solution still exists after each choice. Precomputing a suffix array is a standard way to provide this "future-proof" guarantee.