Find the shortest superstring ii

String

48.8% acceptance

Mar 31, 2026

You are given two strings, s1 and s2. Return the shortest possible string that contains both s1 and s2 as substrings. If there are multiple valid answers, return any one of them. A substring is a contiguous sequence of characters within a string.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn shortest_superstring(s1: String, s2: String) -> String {
    // Find shortest string containing both s1 and s2 as substrings.
    // Check if one contains the other. Otherwise, find max overlap.
    
    if s1.contains(&s2) { return s1; }
    if s2.contains(&s1) { return s2; }
    
    let b1 = s1.as_bytes();
    let b2 = s2.as_bytes();
    
    // Find max overlap: s1 suffix matches s2 prefix
    let mut overlap1 = 0;
    for len in (1..=b1.len().min(b2.len())).rev() {
      if b1[b1.len() - len..] == b2[..len] {
        overlap1 = len;
        break;
      }
    }
    
    // Find max overlap: s2 suffix matches s1 prefix
    let mut overlap2 = 0;
    for len in (1..=b1.len().min(b2.len())).rev() {
      if b2[b2.len() - len..] == b1[..len] {
        overlap2 = len;
        break;
      }
    }
    
    if overlap1 >= overlap2 {
      // s1 + s2[overlap1..]
      format!("{}{}", s1, &s2[overlap1..])
    } else {
      // s2 + s1[overlap2..]
      format!("{}{}", s2, &s1[overlap2..])
    }
  }
}