We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Frequencies of Shortest Supersequences

Difficulty: Hard

Problem Description

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.

Key Insights

  • A shortest common supersequence must include all characters from the input strings while maintaining their relative order.
  • The problem specifically requires identifying SCSs that are not permutations of each other, which means that we need to track character frequencies.
  • The maximum number of unique characters is limited to 16, allowing for efficient frequency representation using an array of size 26 (for each letter of the alphabet).
  • The strings have a fixed length of 2, simplifying the combination process.
  • We can generate potential SCSs by combining the characters of the input words and ensuring we maintain their relative order.

Space and Time Complexity

Time Complexity: O(n * 2^n) where n is the number of input words. This accounts for generating combinations of characters and checking for permutations. Space Complexity: O(1) for storing frequency arrays since the size is constant (26).

Solution

To solve the problem, we can use a combination of bit manipulation and enumeration to generate character combinations that represent the SCSs. We will maintain frequency counts for each unique combination of characters. The approach involves:

  1. Using a bitmask to represent inclusion of characters from the given words.
  2. Generating all possible combinations of characters while ensuring that the combinations are valid SCSs.
  3. Filtering out permutations by using a set to store unique frequency arrays.

Code Solutions

from itertools import combinations
from collections import defaultdict

def frequencies_of_shortest_supersequences(words):
    freq_set = set()
    max_freq = [0] * 26

    for word in words:
        for char in word:
            max_freq[ord(char) - ord('a')] += 1

    # Create a frequency representation of the total maximum frequencies
    freq_set.add(tuple(max_freq))

    # Gather all unique SCS frequencies
    for i in range(len(words)):
        for j in range(i + 1, len(words)):
            combined_freq = [0] * 26
            for char in words[i] + words[j]:
                combined_freq[ord(char) - ord('a')] += 1
            freq_set.add(tuple(combined_freq))

    return [list(freq) for freq in freq_set]
← Back to All Questions