Shortest string that contains three strings

String Greedy Enumeration

31.5% acceptance

Feb 25, 2026

371

295

Given three strings a, b, and c, your task is to find a string that has the minimum length and contains all three strings as substrings. If there are multiple such strings, return the lexicographically smallest one. Return a string denoting the answer to the problem. Notes A string a is lexicographically smaller than a string b (of the same length) if in the first position where a and b differ, string a has a letter that appears earlier in the alphabet than the corresponding letter in b. A substring is a contiguous sequence of characters within a string.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_string(a: String, b: String, c: String) -> String {
    fn merge(s1: &str, s2: &str) -> String {
      if s1.contains(s2) { return s1.to_string(); }
      let max_ov = s1.len().min(s2.len());
      for l in (1..=max_ov).rev() {
        if s1.ends_with(&s2[..l]) {
          return format!("{}{}", s1, &s2[l..]);
        }
      }
      format!("{}{}", s1, s2)
    }
    let strs = [a.as_str(), b.as_str(), c.as_str()];
    let perms: [[usize; 3]; 6] = [
      [0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,0,1],[2,1,0]
    ];
    let mut best: Option<String> = None;
    for &[i, j, k] in &perms {
      let t1 = merge(strs[i], strs[j]);
      let t2 = merge(&t1, strs[k]);
      best = Some(match best {
        None => t2,
        Some(b) => {
          if t2.len() < b.len() || (t2.len() == b.len() && t2 < b) { t2 } else { b }
        }
      });
    }
    best.unwrap()
  }
}