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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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

Output: [0,1,2]

Explanation:

The lexicographically smallest valid sequence of indices is `[0, 1, 2]`:

  * Change `word1[0]` to `'a'`.
  * `word1[1]` is already `'b'`.
  * `word1[2]` is already `'c'`.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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'`.
  * Change `word1[2]` to `'b'`.
  * `word1[4]` is already `'c'`.

Example 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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 * 10^5
  • word1 and word2 consist only of lowercase English letters.

Solution

Method 1 – Greedy Two-Pointer with One Mismatch

Intuition

To form a string almost equal to word2 by picking indices from word1, we want the lexicographically smallest sequence. This means always picking the smallest possible index for each character, allowing at most one mismatch (where we can change a character to match word2).

Approach

  1. Use two pointers: one for word1 and one for word2.
  2. For each position in word2, try to match the next character in word1 as early as possible.
  3. Allow at most one mismatch: if a character in word1 does not match word2, skip it once (count as a change), and continue.
  4. Track the sequence of indices and ensure only one mismatch is used.
  5. If a valid sequence is found, return it; otherwise, return an empty array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<int> smallestValidSequence(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        vector<int> ans;
        int changes = 0, i = 0, j = 0;
        while (i < n && j < m) {
            if (word1[i] == word2[j]) {
                ans.push_back(i);
                ++i; ++j;
            } else if (changes == 0) {
                ans.push_back(i);
                ++i; ++j;
                ++changes;
            } else {
                ++i;
            }
        }
        if (j == m && (changes <= 1)) return ans;
        return {};
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func smallestValidSequence(word1, word2 string) []int {
    n, m := len(word1), len(word2)
    ans := []int{}
    changes, i, j := 0, 0, 0
    for i < n && j < m {
        if word1[i] == word2[j] {
            ans = append(ans, i)
            i++; j++
        } else if changes == 0 {
            ans = append(ans, i)
            i++; j++
            changes++
        } else {
            i++
        }
    }
    if j == m && changes <= 1 {
        return ans
    }
    return []int{}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int[] smallestValidSequence(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        List<Integer> ans = new ArrayList<>();
        int changes = 0, i = 0, j = 0;
        while (i < n && j < m) {
            if (word1.charAt(i) == word2.charAt(j)) {
                ans.add(i); i++; j++;
            } else if (changes == 0) {
                ans.add(i); i++; j++; changes++;
            } else {
                i++;
            }
        }
        if (j == m && changes <= 1) {
            return ans.stream().mapToInt(x -> x).toArray();
        }
        return new int[0];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun smallestValidSequence(word1: String, word2: String): IntArray {
        val n = word1.length; val m = word2.length
        val ans = mutableListOf<Int>()
        var changes = 0; var i = 0; var j = 0
        while (i < n && j < m) {
            if (word1[i] == word2[j]) {
                ans.add(i); i++; j++
            } else if (changes == 0) {
                ans.add(i); i++; j++; changes++
            } else {
                i++
            }
        }
        return if (j == m && changes <= 1) ans.toIntArray() else intArrayOf()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

def smallest_valid_sequence(word1: str, word2: str) -> list[int]:
    n, m = len(word1), len(word2)
    ans: list[int] = []
    changes = 0
    i = j = 0
    while i < n and j < m:
        if word1[i] == word2[j]:
            ans.append(i)
            i += 1; j += 1
        elif changes == 0:
            ans.append(i)
            i += 1; j += 1
            changes += 1
        else:
            i += 1
    if j == m and changes <= 1:
        return ans
    return []
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn smallest_valid_sequence(word1: String, word2: String) -> Vec<i32> {
        let n = word1.len();
        let m = word2.len();
        let w1 = word1.as_bytes();
        let w2 = word2.as_bytes();
        let mut ans = vec![];
        let (mut i, mut j, mut changes) = (0, 0, 0);
        while i < n && j < m {
            if w1[i] == w2[j] {
                ans.push(i as i32); i += 1; j += 1;
            } else if changes == 0 {
                ans.push(i as i32); i += 1; j += 1; changes += 1;
            } else {
                i += 1;
            }
        }
        if j == m && changes <= 1 { ans } else { vec![] }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    smallestValidSequence(word1: string, word2: string): number[] {
        const n = word1.length, m = word2.length;
        const ans: number[] = [];
        let changes = 0, i = 0, j = 0;
        while (i < n && j < m) {
            if (word1[i] === word2[j]) {
                ans.push(i); i++; j++;
            } else if (changes === 0) {
                ans.push(i); i++; j++; changes++;
            } else {
                i++;
            }
        }
        if (j === m && changes <= 1) return ans;
        return [];
    }
}

Complexity

  • ⏰ Time complexity: O(n), as we scan both strings once.
  • 🧺 Space complexity: O(m), for the answer array.