Problem

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 thatword becomes valid.

A string is called valid if it can be formed by concatenating the string “abc” several times.

Examples

Example 1

1
2
3

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 "**a** b**c** ".

Example 2

1
2
3

Input: word = "aaa"
Output: 6
Explanation: Insert letters "b" and "c" next to each "a" to obtain the valid string "a**bc** a**bc** a**bc** ".

Example 3

1
2
3

Input: word = "abc"
Output: 0
Explanation: word is already valid. No modifications are needed.

Constraints

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

Solution

Method 1 – Greedy Pattern Matching

Intuition

A valid string must be made up of repeating “abc” patterns. To make the string valid, we need to insert the minimum number of characters so that every substring of length 3 forms “abc”. We can process the string in chunks of 3 and count the missing characters for each chunk.

Approach

  1. Iterate through the string in steps of 3.
  2. For each chunk, compare with “abc” and count the number of mismatches.
  3. Sum up the total number of insertions needed.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int addMinimum(String word) {
        int ans = 0;
        for (int i = 0; i < word.length(); i += 3) {
            String pat = "abc";
            for (int j = 0; j < 3; ++j) {
                if (i + j >= word.length() || word.charAt(i + j) != pat.charAt(j)) ans++;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def add_minimum(word: str) -> int:
    ans = 0
    pat = "abc"
    n = len(word)
    i = 0
    while i < n:
        for j in range(3):
            if i + j >= n or word[i + j] != pat[j]:
                ans += 1
        i += 3
    return ans

Complexity

  • ⏰ Time complexity: O(n)
    • Each character is checked once.
  • 🧺 Space complexity: O(1)
    • Only a few variables used.