#2645

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Additions to Make Valid String

Determine the minimum insertions required to transform a given string into repeated concatenations of 'abc' using dynamic programming.

string dynamic programming stack greedy

Problem Statement

You are given a string word containing only the letters 'a', 'b', and 'c'. You may insert any number of letters 'a', 'b', or 'c' anywhere in the string. Return the minimum number of insertions needed to transform word into a valid string.

A string is valid if it can be represented as one or more concatenations of the substring 'abc'. For example, 'abc', 'abcabc', and 'abcabcabc' are valid. Example: if word = 'b', you need 2 insertions: an 'a' before and a 'c' after to form 'abc'.

Examples

Example 1

Input: word = "b"

Output: 2

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

Insert letters "b" and "c" next to each "a" to obtain the valid string "abcabcabc".

Example 3

Input: word = "abc"

Output: 0

word is already valid. No modifications are needed.

Constraints

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

Solution Approach

State Tracking with Expected Pointer

Maintain a pointer for the current position in the word and a pointer cycling through 'abc'. Compare characters and insert missing letters to match the expected sequence. Count insertions each time a mismatch occurs.

Greedy Scan with Modular Index

Iterate through the string while tracking the expected character using modulo arithmetic. Whenever the current character does not match, increment the insertion counter and advance the expected pointer accordingly. This handles consecutive repeated letters efficiently.

Dynamic Programming for Accumulated Inserts

Define dp[i] as the minimum insertions required for the first i characters to form valid segments of 'abc'. Update dp using transitions based on the expected next character. This captures all sequences while avoiding unnecessary insertions.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for scanning the string with a pointer, or O(n) using DP for state transitions over word length n. Space complexity is O(1) for greedy approach or O(n) for DP array storing minimal insertions.

What Interviewers Usually Probe

Check if candidates can maintain the cyclic 'abc' state efficiently.
Observe whether they identify insertion points greedily or use dynamic programming.
Look for handling of consecutive missing characters without over-inserting.

Common Pitfalls or Variants

Common pitfalls

Failing to cycle through 'abc' correctly when characters repeat.
Overcounting insertions by not considering the expected sequence state.
Using brute-force insertion checking instead of a DP or pointer-based approach.

Follow-up variants

Allow additional letters beyond 'a', 'b', 'c' and compute minimal deletions to restore validity.
Find the minimal number of deletions instead of insertions to achieve valid repeated 'abc' segments.
Compute minimal insertions when word must form 'xyz' repeated patterns instead of 'abc'.

FAQ

What is the core idea behind Minimum Additions to Make Valid String?

The core idea is to maintain the expected sequence 'abc' while scanning the word and insert missing letters at mismatches to minimize insertions.

Can this problem be solved without dynamic programming?

Yes, a greedy pointer-based approach cycling through 'abc' can achieve optimal results with O(1) extra space.

How do repeated letters affect the insertion count?

Repeated letters may require multiple consecutive insertions to restore the 'abc' pattern, which is why tracking the expected state is essential.

What is the time complexity for a DP solution?

The DP solution runs in O(n) time, where n is the length of the input word, because each character updates a fixed number of state transitions.

Why is this problem considered a state transition dynamic programming pattern?

Because each character depends on the expected next character in the sequence, and DP tracks minimal insertions across these transitions efficiently.

terminal

Solution

Solution 1: Greedy + Two Pointers

We define the string $s$ as `"abc"`, and use pointers $i$ and $j$ to point to $s$ and $word$ respectively.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

Continue Practicing

#2712 minimum cost to make all characters equal #2573 find the string with lcp #2522 partition string into substrings with values at most k