Watch 10 video solutions for Minimum Additions to Make Valid String, a medium level problem involving String, Dynamic Programming, Stack. This walkthrough by Joyjit Codes has 1,239 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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. 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 | 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. |