Find the Lexicographically Smallest Valid Sequence

Find the Lexicographically Smallest Valid Sequence - Problem

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:

The indices are sorted in ascending order.
Concatenating the characters at these indices in 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.

Input & Output

Example 1 — Basic Case

$ Input: word1 = "vsum", word2 = "um"

› Output: [2,3]

💡 Note: We can pick indices [2,3] to get "um" which exactly matches word2. This is the lexicographically smallest valid sequence.

Example 2 — One Character Difference

$ Input: word1 = "hello", word2 = "eo"

› Output: [1,4]

💡 Note: Pick indices [1,4] to get "eo" which exactly matches word2. Other combinations like [0,4] would give "ho" requiring one change.

Example 3 — No Valid Sequence

$ Input: word1 = "abc", word2 = "def"

› Output: []

💡 Note: No sequence of indices can form a string almost equal to "def" since we'd need to change all characters.

Constraints

1 ≤ word1.length, word2.length ≤ 3 × 10³
word1 and word2 consist only of lowercase English letters.

Visualization

Tap to expand

Understanding the Visualization

Input

Two strings word1 and word2

Process

Find indices in word1 that form string almost equal to word2

Output

Lexicographically smallest valid sequence or empty array

Key Takeaway

🎯 Key Insight: Greedily choose the smallest valid index at each position while ensuring future matches remain possible

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to use a greedy approach with lookahead to select the lexicographically smallest valid sequence. We greedily pick the smallest possible index at each step while ensuring the remaining characters can still be matched with at most one total mismatch. Best approach is Greedy with Lookahead. Time: O(n × m), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Lookahead	O(n × m)	O(1)	Greedily pick the smallest valid index at each position with lookahead optimization
Brute Force with Backtracking	O(n^m × m)	O(m)	Try all possible combinations of indices to find the lexicographically smallest valid sequence

Greedy with Lookahead — Algorithm Steps

For each position, try the smallest available index
Use lookahead to check if remaining characters can be matched
Allow at most one mismatch across the entire sequence

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Smallest Index

Start from leftmost available position

Check Feasibility

Use lookahead to verify remaining characters can be matched

Commit Choice

Select index and move to next position

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool canMatchRemaining(const char* word1, const char* word2, int n, int m, int w1Start, int w2Start, int allowedMismatches) {
    if (w2Start >= m) return true;
    
    int remainingChars = m - w2Start;
    int availableChars = n - w1Start;
    
    if (availableChars < remainingChars) return false;
    
    int w1Idx = w1Start;
    int mismatches = 0;
    
    for (int w2Idx = w2Start; w2Idx < m; w2Idx++) {
        bool found = false;
        
        for (int i = w1Idx; i < n; i++) {
            if (word1[i] == word2[w2Idx]) {
                w1Idx = i + 1;
                found = true;
                break;
            }
        }
        
        if (!found) {
            if (mismatches >= allowedMismatches) return false;
            mismatches++;
            if (w1Idx < n) {
                w1Idx++;
            } else {
                return false;
            }
        }
    }
    
    return true;
}

int main() {
    char word1[1001], word2[1001];
    fgets(word1, sizeof(word1), stdin);
    word1[strcspn(word1, "\n")] = 0;
    
    fgets(word2, sizeof(word2), stdin);
    word2[strcspn(word2, "\n")] = 0;
    
    int n = strlen(word1);
    int m = strlen(word2);
    
    int* result = (int*)malloc(m * sizeof(int));
    int resultSize = 0;
    int w1Idx = 0;
    int mismatchesUsed = 0;
    
    for (int w2Pos = 0; w2Pos < m; w2Pos++) {
        bool foundValid = false;
        
        for (int i = w1Idx; i < n; i++) {
            int tempMismatches = mismatchesUsed;
            
            if (word1[i] != word2[w2Pos]) {
                tempMismatches++;
                if (tempMismatches > 1) continue;
            }
            
            if (canMatchRemaining(word1, word2, n, m, i + 1, w2Pos + 1, 1 - tempMismatches)) {
                result[resultSize++] = i;
                w1Idx = i + 1;
                mismatchesUsed = tempMismatches;
                foundValid = true;
                break;
            }
        }
        
        if (!foundValid) {
            printf("[]\n");
            free(result);
            return 0;
        }
    }
    
    printf("[");
    for (int i = 0; i < resultSize; i++) {
        printf("%d", result[i]);
        if (i < resultSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

For each position in word2, scan through word1 indices with lookahead check

✓ Linear Growth

Space Complexity

O(1)

Only use constant extra space for tracking indices and mismatch count

✓ Linear Space

23.4K Views

Medium Frequency

~25 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy with Lookahead — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler