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:
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.
Example 1:
Input: word1 = "vbcca", word2 = "abc"
Output: [0,1,2]
Explanation:
The lexicographically smallest valid sequence of indices is [0, 1, 2]:
word1[0] to 'a'.word1[1] is already 'b'.word1[2] is already 'c'.Example 2:
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'.word1[2] to 'b'.word1[4] is already 'c'.Example 3:
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 * 105word1 and word2 consist only of lowercase English letters.When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
The brute force strategy involves finding every single valid sequence that meets the problem's criteria. Once all possible valid sequences have been generated, we simply compare them all to find the one that is 'smallest' in a dictionary-like order.
Here's how the algorithm would work step-by-step:
class Solution:
def constructDistancedSequence(self, n: int) -> list[int]:
sequence_length = 2 * n - 1
result_sequence = [0] * sequence_length
is_number_used = [False] * (n + 1)
def find_smallest_sequence(current_index):
# When we fill all spots, we have found the first valid sequence, which is the smallest.
if current_index == sequence_length:
return True
if result_sequence[current_index] != 0:
return find_smallest_sequence(current_index + 1)
# We iterate from n down to 1. This greedy choice places larger, more constrained numbers first.
for number_to_try in range(n, 0, -1):
if not is_number_used[number_to_try]:
if number_to_try == 1:
is_number_used[number_to_try] = True
result_sequence[current_index] = number_to_try
if find_smallest_sequence(current_index + 1):
return True
result_sequence[current_index] = 0
is_number_used[number_to_try] = False
else:
partner_index = current_index + number_to_try
# The core rule: a number k > 1 must have its partner placed k spots away.
if partner_index < sequence_length and result_sequence[partner_index] == 0:
is_number_used[number_to_try] = True
result_sequence[current_index] = number_to_try
result_sequence[partner_index] = number_to_try
if find_smallest_sequence(current_index + 1):
return True
# If this path fails, we must undo the move (backtrack) to explore other possibilities.
result_sequence[current_index] = 0
result_sequence[partner_index] = 0
is_number_used[number_to_try] = False
return False
find_smallest_sequence(0)
return result_sequenceThe optimal strategy is to build the sequence of numbers from left to right, like filling in a puzzle. At each empty spot, we make the smallest possible choice that follows the rules. If a choice leads to a dead end, we go back and try the next smallest choice, guaranteeing the first complete sequence we find is the smallest one possible.
Here's how the algorithm would work step-by-step:
class Solution:
def constructDistancedSequence(self, n: int) -> list[int]:
total_sequence_length = 2 * n - 1
sequence_being_built = [0] * total_sequence_length
is_number_used = [False] * (n + 1)
def find_sequence_recursively(position_to_fill: int) -> bool:
if position_to_fill == total_sequence_length:
# If we have filled every single slot, we have found a valid sequence and can stop.
return True
if sequence_being_built[position_to_fill] != 0:
return find_sequence_recursively(position_to_fill + 1)
# We iterate downwards from n to 1. This is a powerful heuristic that tries to place the most
# constrained numbers first (those with the largest required gap), which prunes the search
# space effectively and finds a valid solution faster.
for current_number_to_try in range(n, 0, -1):
if is_number_used[current_number_to_try]:
continue
if current_number_to_try == 1:
is_number_used[current_number_to_try] = True
sequence_being_built[position_to_fill] = current_number_to_try
if find_sequence_recursively(position_to_fill + 1):
return True
is_number_used[current_number_to_try] = False
sequence_being_built[position_to_fill] = 0
else:
second_position = position_to_fill + current_number_to_try
if second_position < total_sequence_length and sequence_being_built[second_position] == 0:
# For any number k>1, we must place its twin k spots away in an empty, valid slot.
is_number_used[current_number_to_try] = True
sequence_being_built[position_to_fill] = current_number_to_try
sequence_being_built[second_position] = current_number_to_try
if find_sequence_recursively(position_to_fill + 1):
return True
# If a path doesn't lead to a solution, we must backtrack by undoing our placements.
is_number_used[current_number_to_try] = False
sequence_being_built[position_to_fill] = 0
sequence_being_built[second_position] = 0
return False
find_sequence_recursively(0)
return sequence_being_built| Case | How to Handle |
|---|---|
| No valid sequence exists because a character in word2 does not appear in word1. | The precomputation of occurrence arrays will fail to find indices for that character, correctly leading to no solution. |
| The only valid solutions require exactly one mismatch. | The algorithm will fail to find an all-match sequence but will proceed to check for one-mismatch solutions and find the valid one. |
| An all-match sequence exists, but a one-mismatch sequence is lexicographically smaller. | The algorithm considers both the all-match sequence and potential one-mismatch sequences, correctly identifying the lexicographically smallest among all valid options. |
| The optimal mismatch occurs at the very first position (k=0). | The systematic check for the mismatch position starts at k=0, ensuring this globally optimal solution is found and compared against others. |
| The optimal solution requires choosing a mismatch index that is smaller than the index that would have been chosen for a match. | The algorithm specifically searches for an improved sequence by finding a mismatch index smaller than the corresponding all-match index, capturing this optimization. |
| word1 consists of only one distinct character, but word2 requires more than one. | The algorithm will be unable to find an index in word1 for the mismatch character required by word2, correctly resulting in no solution found. |
| word2 is very long, with its length close to word1's length. | The solution's linearithmic or linear time complexity with respect to input lengths ensures it performs efficiently even with large inputs. |
| word2 has length 1, the minimum possible. | The loops and boundary conditions of the algorithm handle the single-element case correctly without needing special logic. |