Insert the Fewest Letters to Form Repeated abc Blocks
Company: IBM
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Insert any number of letters a, b, or c anywhere in word without deleting or reordering its existing characters. Return the minimum insertions needed to make the result a concatenation of one or more copies of abc.
```cpp
class Solution {
public:
int addMinimum(string word);
};
```
### Examples
**Example 1:**
```text
Input: word = "acb"
Output: 3
Explanation: Insert letters so the original characters occupy positions 1,3,5 of "abcabc". One three-letter block cannot contain acb in order.
```
**Example 2:**
```text
Input: word = "bcab"
Output: 2
Explanation: Adding an initial a and a final c produces "abcabc".
```
### Constraints
- `1 <= word.length <= 50`.
- Every character is a, b, or c.
### Clarifying Questions
- Can existing characters be removed or rearranged? No; insertions are the only changes.
- Where may new letters be inserted? Anywhere, including either end.
- What is a valid final string? One or more consecutive copies of `"abc"`.
- Must the completed string be returned? No; return only the minimum insertion count.
```hint Check the boundary
Check whether an already valid string needs any insertion.
```
Overview: Insert the fewest a, b or c letters to turn a string into repeated abc blocks without deleting or reordering its original characters.