3435. Frequencies of Shortest Supersequences Hard

1/**
2 * [3435] Frequencies of Shortest Supersequences
3 *
4 * You are given an array of strings words. Find all shortest common supersequences (SCS) of <font face="monospace">words</font> that are not <span data-keyword="permutation-string">permutations</span> of each other.
5 * A shortest common supersequence is a string of minimum length that contains each string in words as a <span data-keyword="subsequence-string-nonempty">subsequence</span>.
6 * 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.
7 *  
8 * <strong class="example">Example 1:
9 * <div class="example-block">
10 * Input: <span class="example-io">words = ["ab","ba"]</span>
11 * 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]]
12 * Explanation:
13 * The two SCSs are "aba" and "bab". The output is the letter frequencies for each one.
14 * </div>
15 * <strong class="example">Example 2:
16 * <div class="example-block">
17 * Input: <span class="example-io">words = ["aa","ac"]</span>
18 * 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]]
19 * Explanation:
20 * The two SCSs are "aac" and "aca". Since they are permutations of each other, keep only "aac".
21 * </div>
22 * <strong class="example">Example 3:
23 * <div class="example-block">
24 * Input: <span class="example-io">words = </span>["aa","bb","cc"]
25 * 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]]
26 * Explanation:
27 * "aabbcc" and all its permutations are SCSs.
28 * </div>
29 *  
30 * Constraints:
31 * 
32 * 	1 <= words.length <= 256
33 * 	words[i].length == 2
34 * 	All strings in words will altogether be composed of no more than 16 unique lowercase letters.
35 * 	All strings in words are unique.
36 * 
37 */
38pub struct Solution {}
39
40// problem: https://leetcode.com/problems/frequencies-of-shortest-supersequences/
41// discuss: https://leetcode.com/problems/frequencies-of-shortest-supersequences/discuss/?currentPage=1&orderBy=most_votes&query=
42
43// submission codes start here
44
45impl Solution {
46    pub fn supersequences(words: Vec<String>) -> Vec<Vec<i32>> {
47        vec![]
48    }
49}
50
51// submission codes end
52
53#[cfg(test)]
54mod tests {
55    use super::*;
56
57    #[test]
58    fn test_3435() {
59    }
60}
61