3435. Frequencies of Shortest Supersequences LeetCode Solution
In this guide, you will get 3435. Frequencies of Shortest Supersequences LeetCode Solution with the best time and space complexity. The solution to Frequencies of Shortest Supersequences problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Frequencies of Shortest Supersequences
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.
Complexity Analysis
Time Complexity: O(2^{16}) = O(1)
Space Complexity: O(26) = O(1)
3435. Frequencies of Shortest Supersequences LeetCode Solution in C++
enum class State { kInit, kVisiting, kVisited };
class Solution {
public:
vector<vector<int>> supersequences(vector<string>& words) {
vector<vector<int>> ans;
const vector<pair<int, int>> edges = getEdges(words);
const vector<int> nodes = getNodes(edges);
const vector<int> letterToIndex = getLetterToIndex(nodes);
vector<vector<int>> graph(nodes.size());
for (const auto& [u, v] : edges)
graph[letterToIndex[u]].push_back(letterToIndex[v]);
for (const auto& doubledSubset : getMinimumSubsets(graph)) {
vector<int> freq(26);
for (const int letter : nodes)
freq[letter] = 1;
for (const int index : doubledSubset)
freq[nodes[index]] = 2;
ans.push_back(freq);
}
return ans;
}
private:
// Returns a list of the minimum subsets of nodes that do not create a cycle
// when skipped.
vector<vector<int>> getMinimumSubsets(const vector<vector<int>>& graph) {
const int n = graph.size();
vector<vector<int>> res;
for (int subsetSize = 0; subsetSize <= n; ++subsetSize) {
vector<bool> combination(n);
fill(combination.end() - subsetSize, combination.end(), true);
do {
vector<int> doubledSubset;
for (int i = 0; i < n; ++i)
if (combination[i])
doubledSubset.push_back(i);
if (!hasCycleSkipping(graph,
{doubledSubset.begin(), doubledSubset.end()}))
res.push_back(doubledSubset);
} while (next_permutation(combination.begin(), combination.end()));
if (!res.empty())
return res;
}
return res;
}
// Returns true if there is a cycle in the `graph` when skipping any edges
// whose both endpoints are in `doubledSubset`.
bool hasCycleSkipping(const vector<vector<int>>& graph,
const unordered_set<int>& doubledSubset) {
vector<State> states(graph.size());
for (int i = 0; i < graph.size(); ++i)
if (hasCycle(graph, i, states, doubledSubset))
return true;
return false;
}
bool hasCycle(const vector<vector<int>>& graph, int u, vector<State>& states,
const unordered_set<int>& doubledSubset) {
if (states[u] == State::kVisiting)
return true;
if (states[u] == State::kVisited)
return false;
states[u] = State::kVisiting;
if (!doubledSubset.contains(u))
for (const int v : graph[u])
if (!doubledSubset.contains(v) &&
hasCycle(graph, v, states, doubledSubset))
return true;
states[u] = State::kVisited;
return false;
}
vector<pair<int, int>> getEdges(const vector<string>& words) {
vector<pair<int, int>> edges;
for (const string& word : words)
edges.push_back({word[0] - 'a', word[1] - 'a'});
return edges;
}
vector<int> getNodes(const vector<pair<int, int>>& edges) {
set<int> nodes;
for (const auto& [u, v] : edges) {
nodes.insert(u);
nodes.insert(v);
}
return {nodes.begin(), nodes.end()};
}
vector<int> getLetterToIndex(const vector<int>& nodes) {
vector<int> letterToIndex(26);
for (int i = 0; i < nodes.size(); ++i)
letterToIndex[nodes[i]] = i;
return letterToIndex;
}
}; /* code provided by PROGIEZ */
3435. Frequencies of Shortest Supersequences LeetCode Solution in Java
enum State { kInit, kVisiting, kVisited }
class Solution {
public List<List<Integer>> supersequences(String[] words) {
List<List<Integer>> ans = new ArrayList<>();
List<int[]> edges = getEdges(words);
List<Integer> nodes = getNodes(edges);
int[] letterToIndex = getLetterToIndex(nodes);
List<Integer>[] graph = new List[nodes.size()];
for (int i = 0; i < nodes.size(); i++)
graph[i] = new ArrayList<>();
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
graph[letterToIndex[u]].add(letterToIndex[v]);
}
for (List<Integer> doubledSubset : getMinimumSubsets(graph)) {
int[] freq = new int[26];
for (final int letter : nodes)
freq[letter] = 1;
for (final int index : doubledSubset)
freq[nodes.get(index)] = 2;
ans.add(Arrays.stream(freq).boxed().collect(Collectors.toList()));
}
return ans;
}
// Returns a list of the minimum subsets of nodes that do not create a cycle
// when skipped.
private List<List<Integer>> getMinimumSubsets(List<Integer>[] graph) {
final int n = graph.length;
List<List<Integer>> res = new ArrayList<>();
for (int subsetSize = 0; subsetSize <= n; ++subsetSize) {
boolean[] combination = new boolean[n];
Arrays.fill(combination, n - subsetSize, n, true);
do {
List<Integer> doubledSubset = new ArrayList<>();
for (int i = 0; i < n; i++)
if (combination[i])
doubledSubset.add(i);
if (!hasCycleSkipping(graph, new HashSet<>(doubledSubset)))
res.add(doubledSubset);
} while (nextPermutation(combination));
if (!res.isEmpty())
return res;
}
return res;
}
// Returns true if there is a cycle in the `graph` when skipping any edges
// whose both endpoints are in `doubledSubset`.
private boolean hasCycleSkipping(List<Integer>[] graph, Set<Integer> doubledSubset) {
State[] states = new State[graph.length];
for (int i = 0; i < graph.length; ++i)
if (hasCycle(graph, i, states, doubledSubset))
return true;
return false;
}
private boolean hasCycle(List<Integer>[] graph, int u, State[] states,
Set<Integer> doubledSubset) {
if (states[u] == State.kVisiting)
return true;
if (states[u] == State.kVisited)
return false;
states[u] = State.kVisiting;
if (!doubledSubset.contains(u))
for (final int v : graph[u])
if (!doubledSubset.contains(v) && hasCycle(graph, v, states, doubledSubset))
return true;
states[u] = State.kVisited;
return false;
}
private List<int[]> getEdges(String[] words) {
List<int[]> edges = new ArrayList<>();
for (final String word : words)
edges.add(new int[] {word.charAt(0) - 'a', word.charAt(1) - 'a'});
return edges;
}
private List<Integer> getNodes(List<int[]> edges) {
TreeSet<Integer> nodes = new TreeSet<>();
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
nodes.add(u);
nodes.add(v);
}
return new ArrayList<>(nodes);
}
private int[] getLetterToIndex(List<Integer> nodes) {
int[] letterToIndex = new int[26];
for (int i = 0; i < nodes.size(); ++i)
letterToIndex[nodes.get(i)] = i;
return letterToIndex;
}
private boolean nextPermutation(boolean[] arr) {
final int n = arr.length;
// From back to front, find the first false followed by true
int i;
for (i = n - 2; i >= 0; --i)
if (!arr[i] && arr[i + 1])
break;
// If no such pair found, we've reached the last permutation
if (i < 0)
return false;
// From back to front, find the first true to swap with arr[i].
for (int j = n - 1; j > i; --j)
if (arr[j] && !arr[i]) {
swap(arr, i, j);
break;
}
// Reverse arr[i + 1..n - 1].
reverse(arr, i + 1, n - 1);
return true;
}
private void reverse(boolean[] arr, int l, int r) {
while (l < r)
swap(arr, l++, r--);
}
private void swap(boolean[] arr, int i, int j) {
boolean temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
} // code provided by PROGIEZ
3435. Frequencies of Shortest Supersequences LeetCode Solution in Python
from enum import Enum
class State(Enum):
kInit = 0
kVisiting = 1
kVisited = 2
class Solution:
def supersequences(self, words: list[str]) -> list[list[int]]:
ans = []
edges = [(string.ascii_lowercase.index(words[0]),
string.ascii_lowercase.index(words[1]))
for words in words]
nodes = sorted({u for u, _ in edges} | {v for _, v in edges})
letterToIndex = {letter: i for i, letter in enumerate(nodes)}
graph = [[] for _ in range(len(nodes))]
for u, v in edges:
graph[letterToIndex[u]].append(letterToIndex[v])
for doubledSubset in self._getMinimumSubsets(graph):
freq = [0] * 26
for letter in nodes:
freq[letter] = 1
for index in doubledSubset:
freq[nodes[index]] = 2
ans.append(freq)
return ans
def _getMinimumSubsets(self, graph: list[list[int]]) -> list[tuple[int]]:
"""
Returns a list of the minimum subsets of nodes that do not create a cycle
when skipped.
"""
n = len(graph)
for subsetSize in range(n + 1):
doubleSubsets = []
for doubledSubset in itertools.combinations(range(n), subsetSize):
if not self._hasCycleSkipping(graph, set(doubledSubset)):
doubleSubsets.append(doubledSubset)
if doubleSubsets:
return doubleSubsets
return []
def _hasCycleSkipping(
self,
graph: list[list[int]],
doubledSubset: set[int]
) -> bool:
"""
Returns True if there is a cycle in the `graph` when skipping any edges
whose both endpoints are in `doubledSubset`.
"""
states = [State.kInit] * len(graph)
def hasCycle(u: int) -> bool:
if states[u] == State.kVisiting:
return True
if states[u] == State.kVisited:
return False
states[u] = State.kVisiting
if u not in doubledSubset:
for v in graph[u]:
if v in doubledSubset:
continue
if hasCycle(v):
return True
states[u] = State.kVisited
return False
return any(hasCycle(i) for i in range(len(graph))) # code by PROGIEZ
