You are given an array of strings words. Find all shortest common supersequences (SCS) of words that are not permutations of each other.
A shortest common supersequence is a string of minimum length that contains each string in words as a subsequence.
Return a 2D array of integers freqs that represent all the SCSs. Each freqs[i] is an array of size 26, representing the frequency of each letter in the lowercase English alphabet for a single SCS. You may return the frequency arrays in any order.
Example 1:
Input: words = ["ab","ba"]
Output: [[1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]
Explanation:
The two SCSs are "aba" and "bab". The output is the letter frequencies for each one.
Example 2:
Input: words = ["aa","ac"]
Output: [[2,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]
Explanation:
The two SCSs are "aac" and "aca". Since they are permutations of each other, keep only "aac".
Example 3:
Input: words = ["aa","bb","cc"]
Output: [[2,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]
Explanation:
"aabbcc" and all its permutations are SCSs.
Constraints:
1 <= words.length <= 256words[i].length == 2words will altogether be composed of no more than 16 unique lowercase letters.words are unique.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:
This search examines every contiguous piece of the longer text. A piece is kept when it contains at least as many of each character as the shorter text requires. Among those pieces it retains only the ones with the smallest length, removes duplicate text, and returns them sorted.
Here's how the algorithm would work step-by-step:
from collections import Counter
def shortest_supersequences_brute_force(longer_string, shorter_string):
shorter_string_counts = Counter(shorter_string)
shortest_supersequences = []
shortest_length_so_far = float('inf')
# Step 1: Examine every possible continuous piece of the longer string.
for start_index in range(len(longer_string)):
for end_index in range(start_index, len(longer_string)):
current_substring = longer_string[start_index : end_index + 1]
current_substring_counts = Counter(current_substring)
is_special = True
# Step 2 & 4: Check if the piece is 'special' by comparing character counts.
for character, required_count in shorter_string_counts.items():
if current_substring_counts.get(character, 0) < required_count:
is_special = False
break
if is_special:
current_length = len(current_substring)
# This is a new shortest special piece, so we discard previous results.
if current_length < shortest_length_so_far:
shortest_length_so_far = current_length
shortest_supersequences = [current_substring]
# This piece matches the shortest length found, so we add it to our list.
elif current_length == shortest_length_so_far:
shortest_supersequences.append(current_substring)
# Remove duplicates from the list of results before returning.
return sorted(list(set(shortest_supersequences)))This count builds a table of shortest common supersequence lengths for every prefix pair of the two sequences. A second table, filled from the finished prefixes backward, adds the number of ways to stay on a shortest alignment. The value in the corner for two empty prefixes is the returned count.
Here's how the algorithm would work step-by-step:
def shortest_supersequence_frequencies(first_sequence, second_sequence):
length_first_sequence = len(first_sequence)
length_second_sequence = len(second_sequence)
scs_length_table = [[0] * (length_second_sequence + 1) for _ in range(length_first_sequence + 1)]
for first_index in range(length_first_sequence + 1):
for second_index in range(length_second_sequence + 1):
if first_index == 0:
scs_length_table[first_index][second_index] = second_index
elif second_index == 0:
scs_length_table[first_index][second_index] = first_index
elif first_sequence[first_index - 1] == second_sequence[second_index - 1]:
scs_length_table[first_index][second_index] = 1 + scs_length_table[first_index - 1][second_index - 1]
else:
scs_length_table[first_index][second_index] = 1 + min(scs_length_table[first_index - 1][second_index], scs_length_table[first_index][second_index - 1])
frequency_count_table = [[0] * (length_second_sequence + 1) for _ in range(length_first_sequence + 1)]
for first_index in range(length_first_sequence, -1, -1):
for second_index in range(length_second_sequence, -1, -1):
if first_index == length_first_sequence and second_index == length_second_sequence:
frequency_count_table[first_index][second_index] = 1
continue
# If characters match, they must be taken together, defining a single shortest path forward.
if first_index < length_first_sequence and second_index < length_second_sequence and first_sequence[first_index] == second_sequence[second_index]:
frequency_count_table[first_index][second_index] = frequency_count_table[first_index + 1][second_index + 1]
else:
# Check if moving along the first sequence stays on a shortest path.
can_use_first = first_index < length_first_sequence and scs_length_table[first_index][second_index] == 1 + scs_length_table[first_index + 1][second_index]
# Check if moving along the second sequence also stays on a shortest path.
can_use_second = second_index < length_second_sequence and scs_length_table[first_index][second_index] == 1 + scs_length_table[first_index][second_index + 1]
if can_use_first:
frequency_count_table[first_index][second_index] += frequency_count_table[first_index + 1][second_index]
if can_use_second:
frequency_count_table[first_index][second_index] += frequency_count_table[first_index][second_index + 1]
return frequency_count_table[0][0]| Case | How to Handle |
|---|---|
| The shorter text is empty | Every one-character piece qualifies, so return each distinct character from the longer text after sorting. |
| The longer text is empty | Return an empty list, because there is no contiguous piece to examine. |
| No piece contains enough copies of every required character | Return an empty list after every window has been rejected. |
| Several pieces tie for the shortest length | Keep all of them, drop exact duplicates, and return the remaining text in sorted order. |
| Both sequences are empty in the alignment count | Return one, because the finished cell of the count table is seeded with one empty alignment. |
| One sequence is empty and the other is not | Return zero, because the backward count never credits a move that only copies leftover characters. |