Minimum Additions to Make Valid String - Solution & Explanation
Problem Statement
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 <= 50wordconsists of letters "a", "b" and "c" only.
Approach Overview
Problem Overview: You are given a string consisting only of the characters 'a', 'b', and 'c'. A valid string is formed by repeating the sequence "abc" any number of times. The task is to compute the minimum number of characters that must be inserted so the final string becomes a sequence of valid abc groups.
Approach 1: Counter to Validate Each Character in Sequence (Greedy) (Time: O(n), Space: O(1))
Traverse the string while tracking which character in the "abc" sequence you expect next. Think of the valid pattern as a cycle: a → b → c → a. For each character in the input, compare it with the expected character. If it matches, move the expected pointer forward. If it does not match, simulate inserting the missing characters until the expected character aligns with the current one. Each simulated insertion increments the answer. This works because the optimal strategy is always to locally fix the sequence before moving forward. The algorithm processes each character once, making it a classic greedy pattern with constant memory.
Approach 2: Character Position Mapping (Alternative Method) (Time: O(n), Space: O(1))
Map each character to its position in the sequence: a=0, b=1, c=2. Iterate through the string and compare the position of the current character with the previous one. If the sequence moves forward (e.g., a→b or b→c), no insertion is needed. If it jumps backward (for example c→a is fine but b→a is invalid), you add the number of characters required to complete the previous abc group. The number of missing characters can be computed with modular arithmetic on the mapped indices. After processing the entire string, add any remaining characters needed to finish the final abc sequence. This approach treats the string like transitions in a cyclic state machine and is often easier to reason about mathematically.
Both strategies operate in linear time because each character is processed exactly once. They also use constant extra memory since only a few counters or indices are maintained. The logic primarily involves character comparisons and arithmetic on the expected sequence.
Recommended for interviews: The greedy sequence-validation approach is the most intuitive and is typically what interviewers expect. It clearly demonstrates how you track a pattern while scanning a string. The position-mapping method is slightly more mathematical and shows deeper insight into sequence transitions, which can stand out in interviews that emphasize pattern recognition or dynamic programming-style state reasoning.
Approach 1: Using Counter to Validate Each Character in Sequence
Iterate through the string, check each character against positions in the sequence 'abc'. An insertion is needed when a character is missing from its expected position in the sequence.
This C program traverses the input string and ensures each expected character ('a', 'b', 'c') is met in sequence or notes the addition needed to complete 'abc' patterns. The sequence is tracked by an index, which resets to zero after 'c' is matched.
Complexity
Time Complexity: O(n), as we traverse each character once.
Space Complexity: O(1), using a constant amount of extra space for counters.
Approach 2: Using Character Position Mapping (Alternative Method)
In this method, maintain counters for how many 'a's, 'b's, and 'c's have been seen, ensuring a valid pattern by correcting whenever necessary.
This C approach counts the number of 'a's, 'b's, and 'c's, ensuring through adjustments and additional inserts that correct numbers of preceding letters maintain the 'abc' validity structure.
Complexity
Time Complexity: O(n), iterating once through the string.
Space Complexity: O(1).
Approach 3: Greedy + Two Pointers
We define the string s as "abc", and use pointers i and j to point to s and word respectively.
If word[j] neq s[i], we need to insert s[i], and we add 1 to the answer; otherwise, it means that word[j] can match with s[i], and we move j one step to the right.
Then, we move i one step to the right, i.e., i = (i + 1) bmod 3. We continue the above operations until j reaches the end of the string word.
Finally, we check whether the last character of word is 'b' or 'a'. If it is, we need to insert 'c' or 'bc', and we add 1 or 2 to the answer and return it.
The time complexity is O(n), where n is the length of the string word. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Using Counter to Validate Each Character in Sequence | Time Complexity: O(n), as we traverse each character once. |
| Using Character Position Mapping (Alternative Method) | Time Complexity: O(n), iterating once through the string. |
| Greedy + Two Pointers | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counter to Validate Each Character in Sequence (Greedy) | O(n) | O(1) | Best general solution. Easy to implement during interviews and clearly follows the expected abc pattern. |
| Character Position Mapping | O(n) | O(1) | Useful when reasoning about cyclic sequences using index math or modular transitions. |
Video Solution
6375. Minimum Additions to Make Valid String - LEETCODE WEEKLY CONTEST 341 (Logic explained) • Joyjit Codes • 1,241 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Additions to Make Valid String easy or hard?
How to solve Minimum Additions to Make Valid String in O(n)?
What is the best approach for Minimum Additions to Make Valid String?
What data structure is used in Minimum Additions to Make Valid String?
What is the time complexity of Minimum Additions to Make Valid String?
Minimum Additions to Make Valid String Python or Java solution approach?
Is Minimum Additions to Make Valid String asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Minimum Additions to Make Valid String with our built-in code editor and test cases.
Practice on FleetCode