LeetCode 2645 - Minimum Additions to Make Valid String

LeetCode Problem 2645

Difficulty: 🟡 Medium
Topics: String, Dynamic Programming, Stack, Greedy

Solution

Problem Understanding

This problem asks us to determine the minimum number of insertions needed to transform a given string word into a valid string. A valid string is defined as one that can be formed by concatenating the sequence "abc" one or more times. In other words, every valid string follows the repeating pattern:

abcabcabc...

We are allowed to insert the characters 'a', 'b', or 'c' anywhere in the string, and we may insert as many characters as necessary. The goal is to compute the smallest number of insertions required so that the final string follows the repeating "abc" structure.

The input consists of a single string word, whose length ranges from 1 to 50. The string contains only the characters 'a', 'b', and 'c'. Since the input size is very small, even less efficient approaches may technically pass, but the problem is designed to reward recognizing the pattern in the valid structure and solving it efficiently.

The key challenge is understanding how characters fit into the repeating "abc" cycle. Since insertions are allowed anywhere, we do not need to preserve chunk boundaries. Instead, we want to determine how many characters are missing to make the sequence consistent with repeated "abc" groups.

Several edge cases are important to recognize upfront. A string containing only one character, such as "a" or "b", requires inserting the missing letters to complete an "abc" block. Strings like "aaa" are tricky because repeated identical letters cannot coexist inside the same "abc" group, meaning each 'a' effectively starts a new group. Another important case is when the input is already valid, such as "abc" or "abcabc", where the answer should be 0.

Approaches

Brute Force Approach

A brute force approach would attempt to construct every possible valid string and determine the minimum number of insertions needed to make word a subsequence of it.

Since a valid string is always composed of repeated "abc" segments, we could generate strings like:

abc
abcabc
abcabcabc
...

For each generated candidate, we would check whether word can be embedded inside it while preserving order. The number of insertions would simply be:

candidate_length - len(word)

We would continue until we find the smallest valid candidate that can contain word.

This approach is correct because it exhaustively searches through all valid target strings and guarantees that the smallest feasible transformation is found. However, it is inefficient because the search space grows unnecessarily, and repeatedly checking subsequences introduces avoidable work.

Key Insight for the Optimal Approach

The important observation is that a valid string always follows the cyclic order:

a → b → c → a → b → c

We can process the string greedily by examining transitions between adjacent characters.

Suppose we are currently at one character and move to the next:

• If the next character comes later in the alphabetic order (a → b, b → c), we are still inside the same "abc" block.
• If the next character is smaller or equal (c → a, b → a, a → a), we must start a new "abc" block.

Once we know how many "abc" groups are needed, computing the answer becomes simple:

insertions = total_required_characters - existing_characters

If there are k groups, the final valid string must have length:

3 * k

Thus:

answer = (3 * k) - len(word)

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Generates candidate valid strings and checks subsequences repeatedly
Optimal	O(n)	O(1)	Counts how many "abc" groups are required using greedy transitions

Algorithm Walkthrough

Optimal Greedy Algorithm

1. Initialize the number of "abc" groups to 1.

Even a single character belongs to at least one group. For example, "a" still requires one "abc" block. 2. Traverse the string from left to right, starting at index 1.

At each position, compare the current character with the previous one. 3. Check whether a new group must begin.

If:

current_character <= previous_character

then the sequence cannot continue within the same "abc" block.

Examples:

• "a" → "b" stays in the same block
• "b" → "c" stays in the same block
• "c" → "a" starts a new block
• "a" → "a" starts a new block
• "b" → "a" starts a new block

Whenever this happens, increment the group count. 4. Compute the total required length.

Each group contributes exactly 3 characters:

total_length = groups * 3

5. Subtract the original string length.

The difference represents how many letters are missing:

answer = total_length - len(word)

Why it works

The core invariant is that every valid string must respect the ordering "a" → "b" → "c" inside each group. Whenever the order decreases or stays the same, it becomes impossible for both characters to belong to the same "abc" segment, so a new segment must begin. By greedily counting the minimum number of required groups, we guarantee the shortest possible valid string, which directly minimizes insertions.

Python Solution

class Solution:
    def addMinimum(self, word: str) -> int:
        groups = 1

        for index in range(1, len(word)):
            if word[index] <= word[index - 1]:
                groups += 1

        return groups * 3 - len(word)

The implementation starts by assuming there is at least one "abc" group. It then iterates through the string and compares each character to the previous one.

Whenever the ordering does not strictly increase, a new group is needed. This matches the greedy observation that valid "abc" blocks must progress in ascending order.

After counting the total groups, the code computes the total length of the required valid string as groups * 3. Finally, it subtracts the original length to determine how many insertions are necessary.

The implementation is concise because the greedy insight eliminates the need for dynamic programming or explicit simulation of insertions.

Go Solution

func addMinimum(word string) int {
    groups := 1

    for i := 1; i < len(word); i++ {
        if word[i] <= word[i-1] {
            groups++
        }
    }

    return groups*3 - len(word)
}

The Go implementation follows exactly the same logic as the Python version. Since Go strings can be indexed directly as bytes, character comparison is straightforward because the input contains only ASCII characters ('a', 'b', 'c').

There are no concerns about integer overflow because the maximum input size is only 50, making all calculations trivially safe within Go's integer range.

Worked Examples

Example 1

word = "b"

We start with:

groups = 1

There are no adjacent characters to compare.

Final calculation:

required_length = 1 × 3 = 3
insertions = 3 - 1 = 2

Result:

2

We can transform:

"b" → "abc"

Example 2

word = "aaa"

Index	Previous	Current	Condition (<=)	Groups
Start	-	a	-	1
1	a	a	Yes	2
2	a	a	Yes	3

Final calculation:

required_length = 3 × 3 = 9
insertions = 9 - 3 = 6

Result:

6

The final valid string becomes:

abcabcabc

Example 3

word = "abc"

Index	Previous	Current	Condition (<=)	Groups
Start	-	a	-	1
1	a	b	No	1
2	b	c	No	1

Final calculation:

required_length = 1 × 3 = 3
insertions = 3 - 3 = 0

Result:

0

The string is already valid.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We scan the string once, comparing adjacent characters
Space	O(1)	Only a few integer variables are used

The algorithm performs a single left-to-right traversal of the string. Each character is processed exactly once, making the runtime linear in the length of the input. Since we only maintain a counter for groups and do not allocate additional data structures proportional to input size, the space complexity remains constant.

Test Cases

solution = Solution()

assert solution.addMinimum("b") == 2  # Single middle character
assert solution.addMinimum("aaa") == 6  # Every 'a' starts a new group
assert solution.addMinimum("abc") == 0  # Already valid

assert solution.addMinimum("a") == 2  # Missing 'b' and 'c'
assert solution.addMinimum("c") == 2  # Missing 'a' and 'b'
assert solution.addMinimum("ab") == 1  # Missing trailing 'c'
assert solution.addMinimum("bc") == 1  # Missing leading 'a'

assert solution.addMinimum("ac") == 1  # Missing 'b'
assert solution.addMinimum("ba") == 4  # Requires two groups
assert solution.addMinimum("cab") == 3  # Transition from c to a

assert solution.addMinimum("abcabc") == 0  # Multiple valid groups
assert solution.addMinimum("aabbcc") == 6  # Repeated characters
assert solution.addMinimum("cccc") == 8  # Every c starts new group

assert solution.addMinimum("abca") == 2  # New group after c
assert solution.addMinimum("bac") == 3  # Mixed ordering

Test Summary

Test	Why
"b"	Verifies single-character middle case
"aaa"	Tests repeated same character
"abc"	Confirms already valid input
"a"	Tests incomplete single group
"c"	Tests ending character only
"ab"	Valid prefix missing one character
"bc"	Missing leading character
"ac"	Missing middle character
"ba"	Requires multiple groups
"cab"	Tests wraparound transition
"abcabc"	Multiple valid concatenations
"aabbcc"	Repeated characters force new groups
"cccc"	Maximum repeated descending behavior
"abca"	Tests transition from c → a
"bac"	Non-trivial ordering case

Edge Cases

Single Character Input

A single character such as "a", "b", or "c" can never form a valid string by itself because every valid block must contain all three letters. A buggy implementation might forget to account for the implicit first group and incorrectly return 0. Our solution initializes groups = 1, ensuring at least one "abc" block always exists.

Repeated Characters

Inputs like "aaa" or "cccc" are easy to mishandle because repeated characters cannot belong to the same "abc" group. Since valid groups require strictly increasing order, equal adjacent characters force a new group. The condition:

word[i] <= word[i - 1]

correctly captures this behavior.

Descending Transitions

Cases such as "ba" or "cab" contain transitions where the sequence moves backward alphabetically. A naive implementation might incorrectly treat these as part of the same group. Our greedy logic recognizes that any decrease means the current "abc" segment has ended and increments the group count accordingly.

Already Valid Strings

Strings like "abc" or "abcabc" should return 0. Since adjacent characters strictly increase within each block and only reset after 'c', the algorithm naturally keeps the group count minimal, resulting in no unnecessary insertions.