DDSA Solutions

3302. Find the Lexicographically Smallest Valid Sequence

MediumView on LeetCode
StringGreedyTwo Pointers

Problem Overview

Pick increasing indices in word1 so the picked characters are almost equal to word2 (at most one mismatch), and among all such index arrays choose the lexicographically smallest.

Intuition

Pick increasing indices in word1 so the picked characters are almost equal to word2 (at most one mismatch), and among all such index arrays choose the lexicographically smallest. Greedy earliest picks work if you know the suffix of word2 is still coverable after a optional skip - that is what the right-to-left last[] table encodes.

Algorithm

  1. 1Build last[j] by matching word2 from the end through word1: last[j] is the latest index used for word2[j] in a greedy reverse match.
  2. 2Scan word1 left to right with j = 0 and canSkip = true.
  3. 3If word1[i] == word2[j], take i into ans and advance j.
  4. 4Else if canSkip and (j is the last position of word2 or i < last[j+1]), take i as the single mismatch, set canSkip false, advance j.
  5. 5Return ans if j reaches word2.Length, else [].

Example Walkthrough

Input: word1 = "vbcca", word2 = "abc"

  1. 1.Reverse match places last so the suffix "bc" remains feasible after an early skip.
  2. 2.Greedy left scan takes indices [0,1,2]: change v->a, keep b, keep c.
  3. 3.That index array is lexicographically smallest among valid sequences.

Output: [0, 1, 2]

Common Pitfalls

  • •Lexicographically smallest refers to the index array, not the string of characters.
  • •You may skip at most once - canSkip must flip to false after the mismatch.
  • •Only skip at i when the remaining exact match of word2[j+1..] still fits after i (i < last[j+1]).
  • •Empty array when even one mismatch cannot rescue an impossible subsequence.
3302.cs
C#
// Approach: Need indices in word1 forming a subsequence almost equal to word2
// (at most one mismatch), and the lexicographically smallest such index array.
// Precompute last[j]: while matching word2 from the end, the latest word1 index
// that can cover word2[j]. Then scan word1 left to right: take exact matches;
// otherwise use the single skip at the earliest index i if the remaining suffix
// of word2 is still matchable (i < last[j+1], or j is the last char).
// Complexity: O(|word1| + |word2|) time and O(|word2|) space.
public class Solution
{
    public int[] ValidSequence(string word1, string word2)
    {
        int[] ans = new int[word2.Length];
        // last[j] := the index i of the last occurrence in word1, where
        // word1[i] == word2[j]
        int[] last = new int[word2.Length];
        Array.Fill(last, -1);

        int i = word1.Length - 1;
        int j = word2.Length - 1;
        while (i >= 0 && j >= 0)
        {
            if (word1[i] == word2[j])
                last[j--] = i;
            --i;
        }

        bool canSkip = true;
        j = 0;
        for (i = 0; i < word1.Length; ++i)
        {
            if (j == word2.Length)
                break;
            if (word1[i] == word2[j])
                ans[j++] = i;
            else if (canSkip && (j == word2.Length - 1 || i < last[j + 1]))
            {
                canSkip = false;
                ans[j++] = i;
            }
        }

        return j == word2.Length ? ans : new int[0];
    }
}
Was this solution helpful?

Related Problems