Frequencies of shortest supersequences

Array String Bit Manipulation Graph Theory Topological Sort Enumeration

22.0% acceptance

Feb 25, 2026

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn supersequences(words: Vec<String>) -> Vec<Vec<i32>> {
    let mut letter_to_idx = [-1i32; 26];
    let mut idx_to_letter: Vec<usize> = Vec::new();
    for w in &words {
      for &b in w.as_bytes() {
        let c = (b - b'a') as usize;
        if letter_to_idx[c] == -1 {
          letter_to_idx[c] = idx_to_letter.len() as i32;
          idx_to_letter.push(c);
        }
      }
    }
    let l = idx_to_letter.len();
    let mut adj = vec![0u32; l];
    let mut self_loops = 0u32;
    for w in &words {
      let bytes = w.as_bytes();
      let a = letter_to_idx[(bytes[0] - b'a') as usize] as usize;
      let b = letter_to_idx[(bytes[1] - b'a') as usize] as usize;
      if a == b { self_loops |= 1u32 << a; }
      else { adj[a] |= 1u32 << b; }
    }
    let is_dag = |excluded: u32| -> bool {
      let mut in_deg = vec![0u32; l];
      for i in 0..l {
        if excluded & (1 << i) != 0 { continue; }
        let mut out = adj[i] & !excluded;
        while out != 0 { let j = out.trailing_zeros() as usize; in_deg[j] += 1; out &= out-1; }
      }
      let mut q: Vec<usize> = (0..l).filter(|&i| excluded&(1<<i)==0 && in_deg[i]==0).collect();
      let mut cnt = 0usize;
      while let Some(u) = q.pop() {
        cnt += 1;
        let mut out = adj[u] & !excluded;
        while out != 0 { let j=out.trailing_zeros() as usize; in_deg[j]-=1; if in_deg[j]==0{q.push(j);} out&=out-1; }
      }
      cnt == (l - excluded.count_ones() as usize)
    };
    let base = self_loops;
    let mut min_extra = l + 1;
    for s in 0u32..=(1u32<<l)-1 {
      if s & base != 0 { continue; }
      if (s.count_ones() as usize) < min_extra && is_dag(base | s) {
        min_extra = s.count_ones() as usize;
      }
    }
    let mut result: Vec<Vec<i32>> = Vec::new();
    let mut seen = std::collections::HashSet::new();
    for s in 0u32..=(1u32<<l)-1 {
      if s & base != 0 { continue; }
      if s.count_ones() as usize != min_extra { continue; }
      if !is_dag(base | s) { continue; }
      let mut freq = vec![0i32; 26];
      for i in 0..l {
        let c = idx_to_letter[i];
        freq[c] = if (base | s) & (1 << i) != 0 { 2 } else { 1 };
      }
      if seen.insert(freq.clone()) { result.push(freq); }
    }
    result
  }
}