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.
- 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 <= 50word consists only of 'a', 'b' and 'c'.
Hints for Minimum Additions to Make Valid String
Hint 1
Think of the target as an endless repetition
abcabcabc…and walk the word through it.Hint 2
Each existing character must land on its matching slot; the slots you skip are the insertions.
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
- Keep
need, the position in the cycle that the next character should occupy (starting ata). - For each character at cycle position
c, add the forward distance fromneedtoc—c - needif it is ahead, otherwise wrapping through the end of the block. - Set
need = (c + 1) % 3and continue. - Finally pad
(3 - need) % 3characters 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
needgives 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 countJava
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