What is the time complexity of Frequencies of Shortest Supersequences?

The optimal solution has a time complexity of O(n*m*k).

What is the space complexity of Frequencies of Shortest Supersequences?

The space complexity is O(n*m*k).

What data structures are used to solve Frequencies of Shortest Supersequences?

This problem uses Array, String, Bit Manipulation, Graph, Topological Sort, Enumeration. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Frequencies of Shortest Supersequences?

Insight 1: Representing the relationships between characters in `words` as a directed graph is key. Each character becomes a node, and each word represents a directed edge from the first character to the second. Insight 2: Strong Connected Components (SCCs) are crucial. Characters within an SCC must appear together in the SCS, but their relative order matters. If an SCC is an Eulerian circuit, then there are multiple valid sequences. Otherwise, characters within the SCC have dependencies that need to be resolved.

Which companies ask LeetCode 3435. Frequencies of Shortest Supersequences in interviews?

This problem is frequently asked at PhonePe.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Frequencies of Shortest Supersequences - LeetCode 3435 Solution

Frequencies of Shortest Supersequences - Complete Solution Guide

Frequencies of Shortest Supersequences is LeetCode problem 3435, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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.

Detailed Explanation

The problem asks us to find all shortest common supersequences (SCS) of a given array of strings `words`, where each string in `words` has a length of 2. An SCS is a string of minimal length that contains each string in `words` as a subsequence. The crucial point is to return the frequency of each letter in the lowercase English alphabet for each distinct SCS, avoiding permutations of the same SCS. For example, if the SCSs are "aba" and "bab", the output should be [[1, 2, 0, ...], [2, 1, 0, ...]]. If SCSs are "aac" and "aca", since they are permutations, only keep "aac". The input strings consist of lowercase English letters, and all strings in `words` are unique.

Solution Approach

The solution involves constructing a directed graph from the input `words`, where nodes are characters and edges represent the order between characters within each word. Then, it identifies the strongly connected components (SCCs) within this graph. For each SCC, it determines the possible frequency counts of characters, considering whether the SCC forms an Eulerian circuit. Finally, it combines the frequency counts of different SCCs to generate distinct frequency counts for the shortest common supersequences. The use of Tarjan's algorithm finds SCC, and special handling is added when the SCC is an Eulerian circuit.

Step-by-Step Algorithm

Step 1: Build a directed graph where nodes represent unique characters, and edges (u, v) represent the fact that the word 'uv' exists in the input. Also, store the edges for future use.
Step 2: Find all Strongly Connected Components (SCCs) of the graph using Tarjan's algorithm. This groups characters that must appear in some order together.
Step 3: For each SCC, determine the possible character frequency counts that can form the shortest subsequence for that SCC. This involves two cases: a) If the SCC is of size 1, calculate loops that may occur from edges in the input and set frequencies. b) If the SCC has size > 1, then it needs to check whether it is an Eulerian circuit or not. i) Eulerian Circuit: The characters can appear in multiple sequence due to the circuit itself; thus, add an extra count for each char. ii) Not Eulerian Circuit: Calculate frequencies based on in-degree and out-degree.
Step 4: Combine the possible character frequency counts from all SCCs to build the final character frequency counts for each SCS using combinatorics.
Step 5: Return the distinct frequency counts for the shortest common supersequences.

Key Insights

Insight 1: Representing the relationships between characters in `words` as a directed graph is key. Each character becomes a node, and each word represents a directed edge from the first character to the second.
Insight 2: Strong Connected Components (SCCs) are crucial. Characters within an SCC must appear together in the SCS, but their relative order matters. If an SCC is an Eulerian circuit, then there are multiple valid sequences. Otherwise, characters within the SCC have dependencies that need to be resolved.
Insight 3: Permutations of SCSs must be avoided by only storing unique frequency counts of the SCS strings.
Insight 4: Each distinct SCS character composition corresponds to a unique sequence combination, and the minimum composition needs to be found based on graph constraints.

Complexity Analysis

Time Complexity: O(n*m*k)

Space Complexity: O(n*m*k)

Topics

This problem involves: Array, String, Bit Manipulation, Graph, Topological Sort, Enumeration.

Companies

Asked at: PhonePe.

Frequencies of Shortest Supersequences | LeetCode 3435

Hard

Array String Bit Manipulation Graph Topological Sort Enumeration

Time: O(n*m*k)Space: O(n*m*k)

Solution Code

Available in:

import java.util.*;

class Solution {
    public List<List<Integer>> supersequences(String[] words) {
        Set<Character> chars = new HashSet<>();
        for (String word : words) {
            chars.add(word.charAt(0));
            chars.add(word.charAt(1));
        }

        List<Character> sortedChars = new ArrayList<>(chars);
        Collections.sort(sortedChars);
        Map<Character, Integer> charToIndex = new HashMap<>();
        Map<Integer, Character> indexToChar = new HashMap<>();
        for (int i = 0; i < sortedChars.size(); i++) {
            charToIndex.put(sortedChars.get(i), i);
            indexToChar.put(i, sortedChars.get(i));
        }

        int n = sortedChars.size();

        if (n == 0) {
            return new ArrayList<>();
        }

        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int i = 0; i < n; i++) {
            adj.put(i, new ArrayList<>());
        }
        List<int[]> edges = new ArrayList<>();
        for (String word : words) {
            int u = charToIndex.get(word.charAt(0));
            int v = charToIndex.get(word.charAt(1));
            adj.get(u).add(v);
            edges.add(new int[]{u, v});
        }

        int[] ids = new int[n];
        Arrays.fill(ids, -1);
        int[] low = new int[n];
        Arrays.fill(low, -1);
        boolean[] onStack = new boolean[n];
        Deque<Integer> stack = new ArrayDeque<>();
        int[] at = {0};
        List<List<Integer>> sccs = new ArrayList<>();

        class DFS {
            void dfs(int u) {
                stack.push(u);
                onStack[u] = true;
                ids[u] = low[u] = at[0]++;

                for (int v : adj.get(u)) {
                    if (ids[v] == -1) {
                        dfs(v);
                    }
                    if (onStack[v]) {
                        low[u] = Math.min(low[u], low[v]);
                    }
                }

                if (ids[u] == low[u]) {
                    List<Integer> scc = new ArrayList<>();
                    while (!stack.isEmpty()) {
                        int node = stack.pop();
                        onStack[node] = false;
                        scc.add(node);
                        if (node == u) break;
                    }
                    sccs.add(scc);
                }
            }
        }

        DFS dfsHelper = new DFS();
        for (int i = 0; i < n; i++) {
            if (ids[i] == -1) {
                dfsHelper.dfs(i);
            }
        }

        List<List<List<Integer>>> sccFreqOptionsList = new ArrayList<>();

        for (List<Integer> scc : sccs) {
            List<List<Integer>> options = new ArrayList<>();
            if (scc.size() == 1) {
                int u = scc.get(0);
                char charU = indexToChar.get(u);
                int numLoops = 0;
                for (int[] edge : edges) {
                    if (edge[0] == u && edge[1] == u) {
                        numLoops++;
                    }
                }
                List<Integer> freq = new ArrayList<>(Collections.nCopies(26, 0));
                freq.set(charU - 'a', numLoops + 1);
                options.add(freq);
            } else {
                Map<Integer, Integer> inDegreeScc = new HashMap<>();
                Map<Integer, Integer> outDegreeScc = new HashMap<>();

                Set<Integer> sccSet = new HashSet<>(scc);
                for (int[] edge : edges) {
                    if (sccSet.contains(edge[0]) && sccSet.contains(edge[1])) {
                        outDegreeScc.put(edge[0], outDegreeScc.getOrDefault(edge[0], 0) + 1);
                        inDegreeScc.put(edge[1], inDegreeScc.getOrDefault(edge[1], 0) + 1);
                    }
                }

                boolean isEulerianCircuit = true;
                for (int node : scc) {
                    if (outDegreeScc.getOrDefault(node, 0) != inDegreeScc.getOrDefault(node, 0)) {
                        isEulerianCircuit = false;
                        break;
                    }
                }

                if (isEulerianCircuit) {
                    List<Integer> baseFreq = new ArrayList<>(Collections.nCopies(26, 0));
                    for (int node : scc) {
                        baseFreq.set(indexToChar.get(node) - 'a', inDegreeScc.getOrDefault(node, 0));
                    }

                    for (int startNode : scc) {
                        List<Integer> freq = new ArrayList<>(baseFreq);
                        freq.set(indexToChar.get(startNode) - 'a', freq.get(indexToChar.get(startNode) - 'a') + 1);
                        options.add(freq);
                    }
                } else {
                    List<Integer> freq = new ArrayList<>(Collections.nCopies(26, 0));
                    for (int node : scc) {
                        int f = inDegreeScc.getOrDefault(node, 0) + Math.max(0, outDegreeScc.getOrDefault(node, 0) - inDegreeScc.getOrDefault(node, 0));
                        freq.set(indexToChar.get(node) - 'a', f);
                    }
                    options.add(freq);
                }
            }
            sccFreqOptionsList.add(options);
        }

        Set<List<Integer>> finalFreqsSet = new HashSet<>();
        finalFreqsSet.add(new ArrayList<>(Collections.nCopies(26, 0)));

        for (List<List<Integer>> sccOptions : sccFreqOptionsList) {
            Set<List<Integer>> newFreqsSet = new HashSet<>();
            for (List<Integer> existingFreq : finalFreqsSet) {
                for (List<Integer> sccFreq : sccOptions) {
                    List<Integer> newFreq = new ArrayList<>();
                    for (int i = 0; i < 26; i++) {
                        newFreq.add(existingFreq.get(i) + sccFreq.get(i));
                    }
                    newFreqsSet.add(newFreq);
                }
            }
            finalFreqsSet = newFreqsSet;
        }

        return new ArrayList<>(finalFreqsSet);
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 3435: Frequencies of Shortest Supersequences - Detailed explanation and solution approaches.

Topics

Array String Bit Manipulation Graph Topological Sort Enumeration

Companies

PhonePe

Stats

Difficulty:Hard

Languages:4

Companies:1

Problem #:3435

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Build a directed graph where nodes represent unique characters, and edges (u, v) represent the fact that the word 'uv' exists in the input. Also, store the edges for future use.
2
Step 2: Find all Strongly Connected Components (SCCs) of the graph using Tarjan's algorithm. This groups characters that must appear in some order together.
3
Step 3: For each SCC, determine the possible character frequency counts that can form the shortest subsequence for that SCC. This involves two cases: a) If the SCC is of size 1, calculate loops that may occur from edges in the input and set frequencies. b) If the SCC has size > 1, then it needs to check whether it is an Eulerian circuit or not. i) Eulerian Circuit: The characters can appear in multiple sequence due to the circuit itself; thus, add an extra count for each char. ii) Not Eulerian Circuit: Calculate frequencies based on in-degree and out-degree.
4
Step 4: Combine the possible character frequency counts from all SCCs to build the final character frequency counts for each SCS using combinatorics.
5
Step 5: Return the distinct frequency counts for the shortest common supersequences.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n*m*k)

💾

Space Complexity

O(n*m*k)

📝

Why?

The time complexity is dominated by the construction of the graph and the final combination of character frequencies. The space complexity comes from storing the graph, SCCs, and final distinct frequency counts. The number of distinct frequency counts can, in the worst case, be exponential in the number of SCCs.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Dynamic Programming

Dynamic programming could potentially be used to find the shortest common supersequence. However, due to constraints avoiding permutations of answers, it would be challenging to efficiently implement.

Time: Potentially exponential, as avoiding permutations increases complexity.Space: Potentially exponential.

Trade-offs: This is likely more complex to implement and less efficient than the graph-based approach due to the need to avoid permutations of SCSs. The graph-based approach naturally handles dependencies and simplifies frequency calculation.

✨

Key Insights

1Insight 1: Representing the relationships between characters in `words` as a directed graph is key. Each character becomes a node, and each word represents a directed edge from the first character to the second.
2Insight 2: Strong Connected Components (SCCs) are crucial. Characters within an SCC must appear together in the SCS, but their relative order matters. If an SCC is an Eulerian circuit, then there are multiple valid sequences. Otherwise, characters within the SCC have dependencies that need to be resolved.
3Insight 3: Permutations of SCSs must be avoided by only storing unique frequency counts of the SCS strings.
4Insight 4: Each distinct SCS character composition corresponds to a unique sequence combination, and the minimum composition needs to be found based on graph constraints.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Graph

Nodes connected by edges. Like a social network or city map!

String

A sequence of characters. Like a word or sentence in programming!

Edge Cases

Edge case 1: Empty input (`words` is empty). The solution gracefully handles this by returning an empty result.
Edge case 2: All strings are same, resulting in the same character repeated (e.g., ["aa", "aa"]). The graph will only contain one node. The loop handling in the SCC of size 1 correctly calculates the required frequency.
Edge case 3: When the graph is not connected. The Tarjan algorithm correctly identifies all SCCs even if the graph is disconnected.
Edge case 4: When there are multiple SCS which are permutation of each other. The set structure makes sure only distinct frequencies count of SCS are stored.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not correctly identifying and handling strongly connected components. The graph structure and Tarjan's Algorithm are essential for this.

✗Common mistake 2: Failing to account for the different sequences for characters in an Eulerian circuit SCC.

✗Common mistake 3: Generating and including permutations of SCS in the final result. Using a `set` to ensure distinct frequency count avoids this.

✗Common mistake 4: Incorrectly accounting for edge cases like empty input or self-loops.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Bioinformatics - Aligning DNA sequences or finding the shortest sequence containing several known motifs.

🏦Real-world scenario 2: Text editing - Finding the shortest way to combine edits from different users into a single document while preserving the order of changes.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Hard problems often combine multiple techniques. Break the problem into sub-problems.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

👨‍💻 From Experience

I encountered a variation of this problem in a system design interview. The key was recognizing the underlying pattern.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: June 16, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 13

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 6

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

What is the sliding window technique for string problems?

Sliding window maintains a "window" of characters with two pointers. Expand the right pointer to include characters, shrink from left when window violates constraints. Useful for substring problems, anagrams, and longest/shortest substring with properties.

Is it okay to not fully solve hard problems in interviews?

Yes! Interviewers care more about your problem-solving process than the final answer. Demonstrate: clear communication, systematic approach, ability to recognize when to pivot strategies, and graceful handling of hints. Partial progress with good reasoning is valued.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Frequencies of Shortest Supersequences"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether string techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?