Minimum Additions to Make Valid String — Medium Problem & Solution

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.

Difficulty: Medium
Topics: Strings, Dynamic Programming, Greedy, Stack
Asked at: Amazon, Google, Zoho
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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'.

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

Keep need, the position in the cycle that the next character should occupy (starting at a).
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.
Set need = (c + 1) % 3 and continue.
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

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue