Minimum Additions to Make Valid String

Medium
863.

Minimum Additions to Make Valid String

Minimum Additions to Make Valid String is a medium coding problem on strings, dynamic programming and greedy, asked in Amazon, Google and Zoho interviews.

A string is valid when it is a concatenation of one or more copies of "abc".

You may insert any character at any position of word. Return the minimum number of insertions needed to make it valid.

Example 1

Input
word = "b"
Output
2
Explanation
Insert an a before and a c after to get "abc".

Example 2

Input
word = "aaa"
Output
6
Explanation
Each a needs its own "bc".

Example 3

Input
word = "abc"
Output
0

Constraints

  • 1 <= word.length <= 50
  • word consists only of 'a', 'b' and 'c'.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} word
 * @return {number}
 */
var addMinimum = function(word) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Additions to Make Valid String — Problem & Solution

Minimum Additions to Make Valid String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Additions to Make Valid String is a medium coding problem on strings, dynamic programming and greedy, asked in Amazon, Google and Zoho interviews.

Problem statement

A string is valid when it is a concatenation of one or more copies of "abc".

You may insert any character at any position of word. Return the minimum number of insertions needed to make it valid.

Example 1

Input: word = "b"
Output: 2
Explanation: Insert an a before and a c after to get "abc".

Example 2

Input: word = "aaa"
Output: 6
Explanation: Each a needs its own "bc".

Example 3

Input: word = "abc"
Output: 0

Constraints

  • 1 <= word.length <= 50
  • word consists only of 'a', 'b' and 'c'.

Hints for Minimum Additions to Make Valid String

  1. Hint 1

    Think of the target as an endless repetition abcabcabc… and walk the word through it.

  2. Hint 2

    Each existing character must land on its matching slot; the slots you skip are the insertions.

  3. Hint 3

    At the end, pad out whatever remains of the current block.

How to solve Minimum Additions to Make Valid String

Model the valid string as a cycle a → b → c → a and walk the word through it. The gap between the slot you need and the character you have is exactly the number of characters that must be inserted.

Approach

  1. Keep need, the position in the cycle that the next character should occupy (starting at a).
  2. For each character at cycle position c, add the forward distance from need to c — c - need if it is ahead, otherwise wrapping through the end of the block.
  3. Set need = (c + 1) % 3 and continue.
  4. Finally pad (3 - need) % 3 characters to close the last block.

Why it works

Insertions never reorder the existing characters, so the word must appear as a subsequence of the target in order — and the cheapest target is the one that advances through the cycle as little as possible at each step. The forward distance is exactly that minimum, and the final padding closes the block the last character opened.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Counting the backward distance when the character is behind need gives a negative or wrong gap — the cycle wraps forwards.
  • Forgetting the trailing padding leaves an incomplete final block.
  • A word that is already a repetition of "abc" needs zero insertions, and the formula must produce that.

Reference solution

Python

def addMinimum(word: str) -> int:
    count = need = 0
    for ch in word:
        c = ord(ch) - 97
        count += (c - need) if c >= need else (3 - need + c)
        need = (c + 1) % 3
    count += (3 - need) % 3
    return count

Java

public static int addMinimum(String word) {
    int count = 0, need = 0;
    for (int i = 0; i < word.length(); i++) {
        int c = word.charAt(i) - 'a';
        count += (c >= need) ? (c - need) : (3 - need + c);
        need = (c + 1) % 3;
    }
    count += (3 - need) % 3;
    return count;
}

C++

int addMinimum(string word) {
    int count = 0, need = 0;
    for (char ch : word) {
        int c = ch - 'a';
        count += (c >= need) ? (c - need) : (3 - need + c);
        need = (c + 1) % 3;
    }
    count += (3 - need) % 3;
    return count;
}

JavaScript

var addMinimum = function(word) {
    var count = 0, need = 0;
    for (var i = 0; i < word.length; i++) {
        var c = word.charCodeAt(i) - 97;
        if (c >= need) count += c - need; else count += 3 - need + c;
        need = (c + 1) % 3;
    }
    count += (3 - need) % 3;
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming