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 <= 50word consists of letters "a", "b" and "c" only. In #2645 Minimum Additions to Make Valid String, a valid string is composed of repeated sequences of "abc". The goal is to determine the minimum number of characters that must be inserted so the given string can be transformed into such a pattern.
A common greedy strategy is to scan the string and track how characters progress within the expected a → b → c order. Whenever the order breaks (for example, when the current character is not the logical next step), it indicates that characters must be inserted to complete the previous sequence. By counting how many valid groups are required and comparing them with the current string length, we can compute the total number of additions needed.
Another way to reason about the problem is to simulate building the pattern using a stack or pointer that checks the expected character and inserts missing ones conceptually. Both approaches process the string in a single pass, leading to efficient performance.
The optimal solutions run in O(n) time with O(1) additional space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy sequence tracking | O(n) | O(1) |
| Stack / pattern simulation | O(n) | O(1) |
Nick White
Use these hints if you're stuck. Try solving on your own first.
Maintain a pointer on word and another pointer on string “abc”.
If the two characters that are being pointed to differ, Increment the answer and the pointer to the string “abc” by one.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The valid pattern always follows the strict order 'a', 'b', 'c', so any deviation clearly indicates missing characters. Greedy scanning identifies these breaks immediately and counts how many insertions are required without backtracking.
Problems involving string patterns, greedy reasoning, and sequence validation are common in FAANG-style interviews. While this exact question may vary, similar problems testing pattern completion and greedy logic appear frequently.
A greedy pointer-based approach is usually sufficient and does not require complex data structures. However, some implementations simulate the process with a stack or expected-character pointer to ensure the sequence follows the 'abc' pattern.
The optimal approach uses a greedy scan of the string while tracking the expected order of characters 'a', 'b', and 'c'. Whenever the order breaks, it indicates missing characters that must be inserted to complete a valid sequence. This allows the problem to be solved in a single pass with constant extra space.