Shortest way to form string

Two Pointers String Binary Search Greedy

61.6% acceptance

Mar 31, 2026

1338

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not). Given two strings source and target, return the minimum number of subsequences of source such that their concatenation equals target. If the task is impossible, return -1.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn shortest_way(source: String, target: String) -> i32 {
    let src: Vec<u8> = source.bytes().collect();
    let tgt: Vec<u8> = target.bytes().collect();
    let mut src_chars = [false; 26];
    for &c in &src { src_chars[(c - b'a') as usize] = true; }
    for &c in &tgt {
      if !src_chars[(c - b'a') as usize] { return -1; }
    }
    let mut count = 0;
    let mut j = 0;
    while j < tgt.len() {
      count += 1;
      let mut i = 0;
      while i < src.len() && j < tgt.len() {
        if src[i] == tgt[j] { j += 1; }
        i += 1;
      }
    }
    count
  }
}