Minimum Additions to Make Valid String

Med

#2405Time: 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.

Patterns

Dynamic Programming Greedy

Data structures

String Stack

Prompt

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 "abc".

Example 2:

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

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

2 approaches with complexity analysis and trade-offs.

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.

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

Walkthrough

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:

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.
If the result for (index, state) is already in our memoization table, we return it directly.
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.
After this, we have effectively matched c. The next expected character state will be (c_val + 1) % 3.
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).
We store this result in the memoization table and return it.

1class Solution {2    private int[][] memo;3    private String word;4 5    public int addMinimum(String word) {6        this.word = word;7        this.memo = new int[word.length()][3];8        for (int[] row : memo) {9            java.util.Arrays.fill(row, -1);10        }11        return solve(0, 0);12    }13 14    private int solve(int index, int state) {15        // Base case: reached the end of the word16        if (index == word.length()) {17            // Insertions needed to complete the last "abc" sequence18            return (3 - state) % 3;19        }20 21        // Return memoized result if available22        if (memo[index][state] != -1) {23            return memo[index][state];24        }25 26        int charVal = word.charAt(index) - 'a';27        28        // Calculate insertions needed at this step29        int insertions = (charVal - state + 3) % 3;30        31        // The new state after matching the current character32        int newState = (charVal + 1) % 3;33        34        // Total insertions = insertions now + insertions for the rest of the string35        int result = insertions + solve(index + 1, newState);36        37        // Memoize and return the result38        memo[index][state] = result;39        return result;40    }41}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public int addMinimum(String word) {3        int insertions = 0;4        // State represents the next character we need: 0 for 'a', 1 for 'b', 2 for 'c'.5        int state = 0; 6 7        for (char c : word.toCharArray()) {8            int charVal = c - 'a';9            10            // Calculate how many characters we need to insert before the current character.11            // This is the cyclic distance from the expected state to the current character's value.12            insertions += (charVal - state + 3) % 3;13            14            // After matching the current character, the state advances to the next one in the cycle.15            state = (charVal + 1) % 3;16        }17        18        // After the loop, if the last sequence is not complete (state != 0),19        // add the remaining characters needed.20        if (state != 0) {21            insertions += (3 - state);22        }23        24        return insertions;25    }26}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  int addMinimum(String word) {4    String s = "abc";5    int ans = 0, n = word.length();6    for (int i = 0, j = 0; j < n; i = (i + 1) % 3) {7      if (word.charAt(j) != s.charAt(i)) {8        ++ans;9      } else {10        ++j;11      }12    }13    if (word.charAt(n - 1) != 'c') {14      ans += word.charAt(n - 1) == 'b' ? 1 : 2;15    }16    return ans;17  }18}

1class Solution {2public:3  int addMinimum(string word) {4    string s = "abc";5    int ans = 0, n = word.size();6    for (int i = 0, j = 0; j < n; i = (i + 1) % 3) {7      if (word[j] != s[i]) {8        ++ans;9      } else {10        ++j;11      }12    }13    if (word[n - 1] != 'c') {14      ans += word[n - 1] == 'b' ? 1 : 2;15    }16    return ans;17  }18};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem