Frequencies of Shortest Supersequences - Practice Coding Problems

Frequencies of Shortest Supersequences - Problem

Array String Bit Manipulation Graph Topological Sort Enumeration Hard

Find All Shortest Common Supersequences

You are given an array of strings words. Your task is to find all shortest common supersequences (SCS) of these 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. Multiple different SCS may exist for the same input.

Return a 2D array of integers freqs where each freqs[i] is an array of size 26, representing the frequency of each letter (a-z) in a unique SCS. You may return the frequency arrays in any order.

Example: For words = ["abc", "ac"], one SCS could be "abc" (frequencies: [1,1,1,0,0,...,0]), but there might be other non-permutation SCS like "abcc" if that's also minimal length.

Input & Output

example_1.py — Basic Case

$ Input: words = ["abc", "ac"]

› Output: [[1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]

💡 Note: The shortest common supersequence is "abc" with length 3. It contains both "abc" and "ac" as subsequences. The frequency array shows 1 occurrence each of 'a', 'b', and 'c'.

example_2.py — Multiple Solutions

$ Input: words = ["ab", "ba"]

› Output: [[1,1,1,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]]

💡 Note: Two different shortest supersequences exist: "abc" and "aba". Both have length 3 but different character frequencies, so both are included in the result.

example_3.py — Single Word

$ Input: words = ["abc"]

› Output: [[1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]

💡 Note: When there's only one word, the shortest common supersequence is the word itself. The frequency array represents the character counts in "abc".

Constraints

1 ≤ words.length ≤ 8
1 ≤ words[i].length ≤ 8
words[i] consists of lowercase English letters only
All strings in words are unique
The total number of characters across all words ≤ 50

Visualization

Tap to expand

Understanding the Visualization

Identify Overlaps

Find where input strings can share characters

Build DP Table

Calculate minimum lengths for all substring combinations

Backtrack Solutions

Enumerate all optimal constructions

Generate Frequencies

Convert each unique supersequence to frequency array

Key Takeaway

🎯 Key Insight: Use dynamic programming to find minimum length, then backtrack through all optimal construction paths to enumerate unique supersequences

Asked in

G Google 25 a Amazon 18 ⊞ Microsoft 12 f Meta 8

This problem requires finding all shortest common supersequences that are not permutations of each other. The optimal approach uses dynamic programming to first determine the minimum length, then backtracking to enumerate all possible constructions. Key insight: merge strings optimally while preserving subsequence relationships for all input words.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force (Generate All Sequences)	O(26^L * n * m)	O(26^L)	Generate all possible sequences and filter for shortest supersequences

Brute Force (Generate All Sequences) — Algorithm Steps

Start with length equal to the longest input word
Generate all possible sequences of current length using a-z
For each sequence, check if all input words are subsequences
Keep track of all valid supersequences of minimum length
Convert each unique supersequence to frequency array
Filter out permutations by comparing frequency arrays

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Length 3

Start with minimum possible length

Test Each Sequence

Check if all words are subsequences

Convert to Frequencies

Transform valid sequences to frequency arrays

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int** freqs;
    int count;
    int capacity;
} Result;

bool isSubsequence(const char* s, const char* word) {
    int i = 0;
    int wordLen = strlen(word);
    
    for (int j = 0; s[j]; j++) {
        if (i < wordLen && s[j] == word[i]) {
            i++;
        }
    }
    return i == wordLen;
}

bool isSupersequence(const char* s, char** words, int wordCount) {
    for (int i = 0; i < wordCount; i++) {
        if (!isSubsequence(s, words[i])) {
            return false;
        }
    }
    return true;
}

int* toFrequency(const char* s) {
    int* freq = (int*)calloc(26, sizeof(int));
    for (int i = 0; s[i]; i++) {
        freq[s[i] - 'a']++;
    }
    return freq;
}

void generateSequences(int length, char* current, int pos, char** words, int wordCount, Result* result) {
    if (pos == length) {
        current[pos] = '\0';
        if (isSupersequence(current, words, wordCount)) {
            if (result->count >= result->capacity) {
                result->capacity *= 2;
                result->freqs = realloc(result->freqs, result->capacity * sizeof(int*));
            }
            result->freqs[result->count] = toFrequency(current);
            result->count++;
        }
        return;
    }
    
    for (char c = 'a'; c <= 'z'; c++) {
        current[pos] = c;
        generateSequences(length, current, pos + 1, words, wordCount, result);
    }
}

int** solution(char** words, int wordCount, int* returnSize) {
    *returnSize = 0;
    if (wordCount == 0) return NULL;
    
    int minLength = 0;
    for (int i = 0; i < wordCount; i++) {
        int len = strlen(words[i]);
        if (len > minLength) minLength = len;
    }
    
    Result result = {NULL, 0, 10};
    result.freqs = malloc(result.capacity * sizeof(int*));
    
    for (int length = minLength; length <= minLength + 3; length++) {
        char* current = malloc((length + 1) * sizeof(char));
        generateSequences(length, current, 0, words, wordCount, &result);
        free(current);
        
        if (result.count > 0) {
            *returnSize = result.count;
            return result.freqs;
        }
    }
    
    free(result.freqs);
    return NULL;
}

Time & Space Complexity

Time Complexity

⏱️

O(26^L * n * m)

Where L is the minimum supersequence length, n is number of words, m is average word length

✓ Linear Growth

Space Complexity

O(26^L)

Space to store all generated sequences

✓ Linear Space

15.8K Views

Medium Frequency

~35 min Avg. Time

420 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force (Generate All Sequences) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler