# Minimum Additions to Make Valid String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-additions-to-make-valid-string)
Canonical: https://scaleengineer.com/dsa/problems/minimum-additions-to-make-valid-string
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String, Stack
---
## Problem
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.

**Example 1:**

**Input:** word = "b"
**Output:** 2
**Explanation:** Insert the letter "a" right before "b", and the letter "c" right next to "b" to obtain the valid string "**a**b**c**".

**Example 2:**

**Input:** word = "aaa"
**Output:** 6
**Explanation:** Insert letters "b" and "c" next to each "a" to obtain the valid string "a**bc**a**bc**a**bc**".

**Example 3:**

**Input:** word = "abc"
**Output:** 0
**Explanation:** word is already valid. No modifications are needed. 

**Constraints:**

* `1 <= word.length <= 50`
* `word` consists of letters "a", "b" and "c" only.

# Approaches
## Recursion with Memoization (Top-Down DP)
This approach models the problem using a recursive structure. We define a function that calculates the minimum insertions for the remainder of the string, given the current state (which character is expected next). To optimize this and avoid re-computing results for the same subproblems, we use a memoization table (a 2D array) to store the outcomes. This transforms the plain recursion into a more efficient dynamic programming solution.
**Time:** O(N), where N is the length of `word`. Each state `(index, state)` is computed only once, and there are N * 3 possible states. · **Space:** O(N), where N is the length of `word`. This is for the memoization table of size N x 3 and the depth of the recursion stack.
**Pros:** The recursive structure with memoization is a standard DP pattern, making it a clear and logical way to solve the problem.; It correctly breaks down the problem into smaller, overlapping subproblems.
**Cons:** Uses O(N) extra space for the memoization table and recursion stack, which is less optimal than the iterative approach.; For very long strings, recursion could lead to a stack overflow error, although not an issue with the given constraints.
### Explanation
The core idea is to define a state by `(index, expected_char_state)` and find the minimum insertions from that state. The state `expected_char_state` can be an integer from 0 to 2, representing 'a', 'b', and 'c' respectively.

The function `solve(index, state)` will work as follows:
1.  If we have processed the entire string (`index == word.length()`), we calculate the final insertions needed to complete the last `"abc"` sequence. If we expect 'a' (`state=0`), 0 insertions are needed. If we expect 'b' (`state=1`), 2 insertions ('b', 'c') are needed. If we expect 'c' (`state=2`), 1 insertion ('c') is needed. This can be generalized to `(3 - state) % 3`.
2.  If the result for `(index, state)` is already in our memoization table, we return it directly.
3.  Otherwise, we take the current character `char c = word.charAt(index)`. We calculate the number of insertions required to satisfy the expectation. For example, if we expect 'a' (`state=0`) and see 'c' (`c_val=2`), we must insert 'a' and 'b'. The number of insertions is `(c_val - state + 3) % 3`.
4.  After this, we have effectively matched `c`. The next expected character state will be `(c_val + 1) % 3`.
5.  The total insertions from the current state is the sum of insertions at this step and the result of the recursive call for the next index and new state: `insertions_at_this_step + solve(index + 1, new_state)`.
6.  We store this result in the memoization table and return it.

```java
class Solution {
    private int[][] memo;
    private String word;

    public int addMinimum(String word) {
        this.word = word;
        this.memo = new int[word.length()][3];
        for (int[] row : memo) {
            java.util.Arrays.fill(row, -1);
        }
        return solve(0, 0);
    }

    private int solve(int index, int state) {
        // Base case: reached the end of the word
        if (index == word.length()) {
            // Insertions needed to complete the last "abc" sequence
            return (3 - state) % 3;
        }

        // Return memoized result if available
        if (memo[index][state] != -1) {
            return memo[index][state];
        }

        int charVal = word.charAt(index) - 'a';
        
        // Calculate insertions needed at this step
        int insertions = (charVal - state + 3) % 3;
        
        // The new state after matching the current character
        int newState = (charVal + 1) % 3;
        
        // Total insertions = insertions now + insertions for the rest of the string
        int result = insertions + solve(index + 1, newState);
        
        // Memoize and return the result
        memo[index][state] = result;
        return result;
    }
}
```
### Algorithm
- The problem can be solved using recursion with memoization, which is a top-down dynamic programming approach.
- We define a function `solve(index, state)` which computes the minimum insertions needed for the suffix of the word starting at `index`, given that the next expected character in the valid sequence corresponds to `state` (where `state` 0='a', 1='b', 2='c').
- **Base Case:** If `index` reaches the end of the string, we've processed all characters. We might need to add characters to complete the last `"abc"` block. The number of insertions needed is `(3 - state) % 3`.
- **Recursive Step:** For the character `word.charAt(index)`, we calculate how many characters we need to insert to make our `state` match this character. This is the cyclic distance between `state` and `word.charAt(index)`. After matching, the new state becomes the one following `word.charAt(index)`, and we recurse for `index + 1`.
- **Memoization:** We use a 2D array `memo[n][3]` to store the results of `solve(index, state)` to avoid redundant calculations. The initial call is `solve(0, 0)`.

## Iterative Greedy Approach (State Machine)
A more optimal approach is to iterate through the string once, maintaining a single state variable that represents the character we currently expect in the valid `"abc"` sequence. This is essentially a state machine. At each character in the input `word`, we greedily calculate the minimum number of insertions needed to match it and then update our state. This avoids the overhead of recursion and extra space for a memoization table.
**Time:** O(N), where N is the length of `word`. We perform a single pass through the string. · **Space:** O(1), as we only use a few variables to keep track of the state and the total insertions, regardless of the input string's size.
**Pros:** Extremely efficient, with optimal O(1) space complexity.; The single-pass iterative solution is fast and avoids recursion overhead.; The code is concise and simple to implement.
**Cons:** The greedy logic, while simple, might be slightly less intuitive to prove correct compared to a formal DP setup for those unfamiliar with state machine patterns.
### Explanation
We can think of building the valid string by consuming characters from the input `word`. We keep track of which character we expect next in the `"abc"` cycle ('a', then 'b', then 'c', then 'a' again). Let's use an integer `state` (0 for 'a', 1 for 'b', 2 for 'c') for this.

We start by expecting 'a' (`state = 0`). We iterate through `word`. When we encounter a character `c`, we see how many characters we need to insert to make our expectation match `c`. For instance, if we expect 'a' (`state=0`) and see 'b' (`c_val=1`), we must insert one character ('a'). The number of insertions is simply `c_val - state`. If we expect 'c' (`state=2`) and see 'a' (`c_val=0`), we must wrap around. This means inserting 'c' to finish the old block, and then we are ready for the new 'a'. The number of insertions can be calculated with modular arithmetic: `(c_val - state + 3) % 3`.

After accounting for the insertions and matching `c`, our next expected character will be the one that follows `c` in the cycle, so we update `state` to `(c_val + 1) % 3`.

Finally, after the loop, we might have an incomplete sequence. We add the final insertions needed to complete it.

```java
class Solution {
    public int addMinimum(String word) {
        int insertions = 0;
        // State represents the next character we need: 0 for 'a', 1 for 'b', 2 for 'c'.
        int state = 0; 

        for (char c : word.toCharArray()) {
            int charVal = c - 'a';
            
            // Calculate how many characters we need to insert before the current character.
            // This is the cyclic distance from the expected state to the current character's value.
            insertions += (charVal - state + 3) % 3;
            
            // After matching the current character, the state advances to the next one in the cycle.
            state = (charVal + 1) % 3;
        }
        
        // After the loop, if the last sequence is not complete (state != 0),
        // add the remaining characters needed.
        if (state != 0) {
            insertions += (3 - state);
        }
        
        return insertions;
    }
}
```
### Algorithm
- This approach uses a greedy strategy with a state machine.
- Initialize `insertions = 0` and a `state` variable to 0 (representing the next expected character 'a').
- Iterate through each character `c` of the input `word`.
- For each `c`, determine its integer value `c_val` (0 for 'a', 1 for 'b', 2 for 'c').
- Calculate the number of insertions needed to bridge the gap between the `state` and `c_val`. This is `(c_val - state + 3) % 3`.
- Add this number to the total `insertions`.
- After matching `c`, update the `state` to be the next character in the sequence: `state = (c_val + 1) % 3`.
- After the loop finishes, the `state` indicates if the last `"abc"` sequence is complete. If `state` is not 0, add the remaining `(3 - state) % 3` insertions.
- Return the total `insertions`.

# Solutions
### Java

```java
class Solution {
public
  int addMinimum(String word) {
    String s = "abc";
    int ans = 0, n = word.length();
    for (int i = 0, j = 0; j < n; i = (i + 1) % 3) {
      if (word.charAt(j) != s.charAt(i)) {
        ++ans;
      } else {
        ++j;
      }
    }
    if (word.charAt(n - 1) != 'c') {
      ans += word.charAt(n - 1) == 'b' ? 1 : 2;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int addMinimum(string word) {
    string s = "abc";
    int ans = 0, n = word.size();
    for (int i = 0, j = 0; j < n; i = (i + 1) % 3) {
      if (word[j] != s[i]) {
        ++ans;
      } else {
        ++j;
      }
    }
    if (word[n - 1] != 'c') {
      ans += word[n - 1] == 'b' ? 1 : 2;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def addMinimum(self, word: str) -> int: s = 'abc' ans, n = 0, len(word) i = j = 0 while j < n: if word[j] != s[i]: ans += 1 else: j += 1 i = (i + 1) % 3 if word[- 1] != 'c': ans += 1 if word[- 1] == 'b' else 2 return ans

```