Shortest uncommon substring in an array

Array Hash Table String Trie

50.0% acceptance

Feb 25, 2026

169

You are given an array arr of size n consisting of non-empty strings. Find a string array answer of size n such that: answer[i] is the shortest substring of arr[i] that does not occur as a substring in any other string in arr. If multiple such substrings exist, answer[i] should be the lexicographically smallest. And if no such substring exists, answer[i] should be an empty string. Return the array answer.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn shortest_substrings(arr: Vec<String>) -> Vec<String> {
    let n = arr.len();
    let mut ans = vec![String::new(); n];
    for i in 0..n {
      let s = &arr[i];
      let m = s.len();
      'outer: for len in 1..=m {
        let mut best: Option<&str> = None;
        for start in 0..=m-len {
          let sub = &s[start..start+len];
          // Check if sub appears in any other arr[j]
          let unique = (0..n).filter(|&j| j != i).all(|j| !arr[j].contains(sub));
          if unique {
            best = Some(match best {
              None => sub,
              Some(b) => if sub < b { sub } else { b },
            });
          }
        }
        if let Some(b) = best {
          ans[i] = b.to_string();
          break 'outer;
        }
      }
    }
    ans
  }
}