We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Additions to Make Valid String

Difficulty: Medium

Problem Description

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.

Key Insights

  • A valid string is made up of repeated patterns of "abc".
  • The characters in the input string must be placed in the correct order to form the "abc" pattern.
  • We can track the expected character at each position in the "abc" cycle.
  • The number of insertions required depends on how many characters are missing to complete the "abc" pattern.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string word. Space Complexity: O(1), since we only use a fixed amount of extra space regardless of the input size.

Solution

To solve the problem, we can use a greedy approach to track the expected character in the "abc" cycle. We iterate through each character in the input string and check if it matches the expected character. If it doesn't match, we count how many insertions are needed to make it valid. We also keep track of the expected character, which cycles through 'a', 'b', and 'c'.

Code Solutions

def minAdditions(word: str) -> int:
    expected = 'a'
    insertions = 0
    
    for char in word:
        while char != expected:
            insertions += 1
            expected = chr(ord(expected) + 1) if expected != 'c' else 'a'
        expected = chr(ord(expected) + 1) if expected != 'c' else 'a'
    
    # Account for any remaining characters in the cycle
    if expected != 'a':
        insertions += (3 - (ord(expected) - ord('a')))
    
    return insertions
← Back to All Questions