Minimum additions to make valid string

String Dynamic Programming Stack Greedy

51.0% acceptance

Feb 25, 2026

591

Given a string word to which you can insert letters "a", "b" or "c" anywhere and any number of times, return the minimum number of letters that must be inserted so that word becomes valid. A string is called valid if it can be formed by concatenating the string "abc" several times.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn add_minimum(word: String) -> i32 {
    let mut cur = 0usize; // position in the concatenated "abcabc..."
    let mut insertions = 0i32;

    for c in word.bytes() {
      let p = (c - b'a') as usize; // position in "abc": 0, 1, or 2
      if p < cur % 3 {
        // Need to start a new group
        insertions += (3 - cur % 3) as i32;
        cur = ((cur / 3) + 1) * 3;
      }
      // Fill the gap within current group
      insertions += (p - cur % 3) as i32;
      cur = (cur / 3) * 3 + p + 1;
    }
    // Close last group
    insertions += ((3 - cur % 3) % 3) as i32;
    insertions
  }
}