Taro Logo

Frequencies of Shortest Supersequences

#9 Most AskedHard
9 views
Topics:
GraphsDynamic ProgrammingBit Manipulation

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 <= 256
  • words[i].length == 2
  • All strings in words will altogether be composed of no more than 16 unique lowercase letters.
  • All strings in words are unique.

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. For the window search, does a piece qualify when it contains at least the required count of every character, with extras allowed?
  2. Should duplicate copies of the same shortest piece be returned only once, in sorted order?
  3. Is the shortest length measured in characters of a contiguous piece of the longer text?
  4. Does the table solution return one count of shortest alignments of two sequences, rather than letter-frequency rows?
  5. Are empty sequences allowed as inputs to either search?

Brute Force Solution

Approach

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:

  1. Count the characters required by the shorter text.
  2. Start the best length as unknown and start the result list empty.
  3. For every start and every end at or after that start, cut out that piece of the longer text.
  4. Count the characters in the piece and reject it when any required character is short.
  5. When the piece is shorter than the best length, replace the result list with that piece alone.
  6. When the piece matches the best length, append it.
  7. Drop duplicate strings and return the remaining pieces in sorted order.

Code Implementation

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)))

Big(O) Analysis

Time Complexity
O(n^3) – There are a quadratic number of start and end pairs in a text of length n. Building the character counts for a piece takes time proportional to the piece length. The lengths of all contiguous pieces add up to a cubic quantity, because each length contributes about n pieces and the lengths run up to n. Comparing a piece with the required counts adds only work proportional to the shorter text, which is dominated by building the counts. The total is therefore O(n^3).
Space Complexity
O(n^2) – The required counts and the counts for the piece currently being checked use space proportional to the alphabet, which does not grow with the text. The result keeps every surviving piece of the winning length. There are at most about n pieces of one fixed length, and each piece holds up to n characters. Duplicate removal stores those same strings again. The extra memory is therefore O(n^2) in the worst case.

Optimal Solution

Approach

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:

  1. Allocate a length table and a count table, both one larger than each sequence in both directions.
  2. Fill the length table from empty prefixes, using the remaining length on either axis.
  3. When the next characters of the two prefixes match, extend the diagonal length by one.
  4. When they differ, extend the cheaper of the two one-sided moves by one.
  5. Seed the finished corner of the count table with one.
  6. Walking backward, copy the diagonal count when the characters at the current positions are equal.
  7. Otherwise add the forward counts for whichever one-step moves preserve the stored shortest length.

Code Implementation

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]

Big(O) Analysis

Time Complexity
O(n * m) – The length table has one row per character of the first sequence plus a border, and one column per character of the second sequence plus a border. Filling each cell inspects only a constant amount of earlier cells. The count table has the same shape and also does constant work per cell, including the two possible forward moves. No cell is recomputed. With n and m the two lengths, the running time is O(n * m).
Space Complexity
O(n * m) – Both tables store a number for every pair of prefixes, including the empty prefixes. That is a rectangular grid whose sides are one larger than the two sequence lengths. The fill uses a handful of index variables beyond those grids. The sequences themselves are the input. The auxiliary space is therefore the two grids, which is O(n * m).

Edge Cases

The shorter text is empty
How to Handle:
Every one-character piece qualifies, so return each distinct character from the longer text after sorting.
The longer text is empty
How to Handle:
Return an empty list, because there is no contiguous piece to examine.
No piece contains enough copies of every required character
How to Handle:
Return an empty list after every window has been rejected.
Several pieces tie for the shortest length
How to Handle:
Keep all of them, drop exact duplicates, and return the remaining text in sorted order.
Both sequences are empty in the alignment count
How to Handle:
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
How to Handle:
Return zero, because the backward count never credits a move that only copies leftover characters.
0/98 completed