Taro Logo

Find the Lexicographically Smallest Valid Sequence

#636 Most AskedMedium
Topics:
ArraysTwo PointersGreedy Algorithms

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.

Example 1:

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:

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:

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

Solution


Clarifying Questions

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:

  1. To clarify the 'almost equal' condition, does this cover both the case of zero differences (an exact match) and the case of exactly one character difference compared to `word2`?
  2. My high-level approach would be to find the lexicographically smallest sequence for a perfect match, and separately, the lexicographically smallest sequence for a single mismatch, and then compare the two results. Is this a sound way to break down the problem?
  3. When constructing a sequence, to keep it lexicographically minimal, my intuition is to greedily pick the smallest possible index at each step. Could this greedy choice at an early stage potentially prevent me from finding a valid sequence for the remaining characters?
  4. For the single-mismatch case, the mismatch could occur at any position in `word2`. To find the overall best solution, should I find the lexicographically smallest sequence for each possible mismatch position and then select the overall minimum among those results?
  5. Regarding the input strings, is it possible for `word2` to contain characters that are completely absent in `word1`?

Brute Force Solution

Approach

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:

  1. Imagine we have a row of empty slots to fill, one for each position in the final sequence.
  2. We start at the first empty slot from the left.
  3. We then try to place one of the numbers we are allowed to use into this slot.
  4. When we place a number larger than one, say 'X', we must also place its twin 'X' positions away. If that second spot is already taken, the placement is invalid, and we must try a different number.
  5. If a placement is valid, we move to the next empty slot and repeat the process with our remaining numbers.
  6. If we get to a slot and find that no number can be placed legally, we backtrack. This means we go back to the previous slot, undo our choice, and try the next option for that spot.
  7. Every time we successfully fill all the slots, we have found a complete, valid sequence. We save this sequence in a list of all solutions.
  8. We continue this process of trying, backtracking, and saving until every single possibility has been explored.
  9. Finally, we look through our complete list of valid sequences and select the one that would appear first if they were sorted like words in a dictionary.

Code Implementation

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_sequence

Big(O) Analysis

Time Complexity
O(n!) – This search fills the sequence from left to right and stops at the first arrangement that meets every placement rule. At an empty position it tries each still-unused value, starting with the largest. The value one occupies only the current position, while every larger value also needs a second open position a fixed distance ahead. Each accepted placement continues through recursion, and a dead end restores the earlier placements before the next value is tried. Every value can be chosen at most once, so the arrangements that may be explored are bounded by the factorial of the input and the worst-case time is O(n!).
Space Complexity
O(n) – The sequence contains one cell for the value one and two cells for every larger value, so its length grows linearly with the input. A table of the same order records which values have already been used. Recursive calls nest once for each cell, and each call stores only a constant amount of extra information. Failed attempts undo their writes in the shared sequence instead of copying it. Auxiliary space is therefore linear, O(n).

Optimal Solution

Approach

The 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:

  1. Imagine we are filling a line of empty slots, one by one, from the beginning to the end.
  2. When we get to the first empty slot, we want to fill it with the smallest number we can.
  3. We look at all the numbers we're allowed to use, and we try to place the smallest available one first.
  4. Each number has a special placement rule: the number '1' is placed by itself, but any other number, let's call it 'X', must be placed as a pair, where the second 'X' is exactly 'X' slots away from the first.
  5. We check if our chosen number can be placed according to its rule without going off the board or landing on an already filled slot.
  6. If it fits, we tentatively place the number (or pair of numbers) and then move on to solve for the rest of the empty slots.
  7. If that choice successfully leads to a complete sequence, we've found our answer! Since we always tried smaller numbers in earlier slots, this must be the lexicographically smallest solution.
  8. If a choice doesn't work out and leads to a dead end, we simply undo that placement and try the next-smallest available number in the original slot.

Code Implementation

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

Big(O) Analysis

Time Complexity
O(n * n!) – The time complexity is determined by the backtracking search. The algorithm must find the correct arrangement of n distinct numbers, which is conceptually similar to exploring permutations, leading to a search space that grows factorially (n!). For each placement decision in the recursive process, the code iterates through up to n possible numbers to find a valid choice. Therefore, the total runtime is the product of the n! possibilities and the O(n) work done at each step, simplifying to O(n * n!).
Space Complexity
O(N) – The algorithm requires an array of size 2*N - 1 to represent the 'line of empty slots' where the sequence is constructed. To track which numbers are available, as described by needing to 'look at all the numbers we're allowed to use', an auxiliary boolean array of size N is necessary. The process of making a choice and 'going back' if it leads to a dead end is implemented via recursion. This recursion creates a call stack that can reach a maximum depth proportional to the number of slots to be filled, resulting in O(N) space.

Edge Cases

No valid sequence exists because a character in word2 does not appear in word1.
How to Handle:
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.
How to Handle:
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.
How to Handle:
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).
How to Handle:
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.
How to Handle:
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.
How to Handle:
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.
How to Handle:
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.
How to Handle:
The loops and boundary conditions of the algorithm handle the single-element case correctly without needing special logic.
0/1037 completed