Smallest Index Sequence Matching a Target with at Most One Change
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
You are given lowercase strings `word1` and `word2`. Choose `word2.length` indices from `word1` in increasing order. Reading the characters at those indices must produce a string that can be made identical to `word2` by changing at most one character.
Return the lexicographically smallest valid array of indices. Compare the index arrays themselves, rather than the strings they select: at the first differing position, the array with the smaller index is smaller. If no valid array exists, return an empty array.
```cpp
class Solution {
public:
vector<int> validSequence(string word1, string word2);
};
```
### Examples
**Example 1:**
```text
Input: word1 = "xacbd", word2 = "abd"
Output: [0,3,4]
Explanation: These indices select "xbd", which differs from "abd" only at its first character. Index 0 is the smallest possible first index; after it, indices 3 and 4 provide the required b and d.
```
**Example 2:**
```text
Input: word1 = "zayc", word2 = "abc"
Output: [1,2,3]
Explanation: The selected string "ayc" needs only y changed to b. Starting with index 0 would spend the one allowed change on z, but there is no b available for the remaining positions.
```
### Constraints
- `1 <= word2.length < word1.length <= 300000`.
- Both strings contain only lowercase English letters.
### Clarifying Questions
- Must one character change? No. An exact match also qualifies.
- Can selected positions be reordered or reused? No. The indices identify distinct positions in increasing order.
- Is the objective to minimize the selected letters? No. Minimize the returned array of indices.
- What is returned if there is no valid selection? An empty array.
### What a Strong Answer Covers
- Preserves the ordering of selected positions and the budget of at most one differing character.
- Establishes that the returned index array is lexicographically smallest, rather than merely valid.
- Handles an impossible selection and the full string-length bounds.
```hint Check whether a choice can be completed
Precompute how much of the target's ending can be matched exactly after each source position. Once the one differing character is selected, every remaining target character must match exactly.
```
Overview: Return the lexicographically smallest increasing index sequence whose selected characters differ from a target in at most one position. Return an empty array if none exists.