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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Additions to Make Valid String

Number: 2736

Difficulty: Medium

Paid? No

Companies: Google, Microsoft, Amazon, Bloomberg

Problem Description

Given a string word consisting only of letters "a", "b", and "c", you are allowed to insert any of these letters anywhere in the string (zero or more times). The goal is to find the minimum number of letters needed to be inserted to transform word into a valid string. A string is considered valid if it can be obtained by concatenating the substring "abc" (i.e. "abcabcabc...").

Key Insights

  • The valid string is always a sequence of "abc" repeated.
  • We can view the problem as "aligning" the given string with the expected pattern "abc".
  • Use a pointer to simulate the expected position in the "abc" cycle.
  • For each character in the input, if it does not match the expected character, count the necessary insertions and adjust the cycle pointer.
  • After processing the input, account for any remaining characters to complete the last "abc" group.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the given string word.
Space Complexity: O(1) as only a few variables are used for the simulation.

Solution

The solution involves simulating the construction of a valid string by iterating through the given word and matching it with the expected sequence "abc". Maintain a pointer (or index) representing the next expected character in the "abc" cycle. For each character in word, if it mismatches the expected letter, insert the missing letters (simulate by incrementing an insertion counter) until the expected letter matches the current character. After processing the entire word, if the cycle is incomplete, add the necessary insertions to complete the final group.
Data structures used: simple integer counters and a string pattern "abc".
Algorithmic approach: Greedy simulation, ensuring that for every character we "fill in" the missing part of the pattern in the most optimal way.

Code Solutions

# Define a function to compute the minimum number of insertions.
def add_min_letters(word: str) -> int:
    expected = "abc"  # valid pattern
    pos = 0          # pointer for the current position in the expected cycle
    insertions = 0   # count of insertions needed
    
    # Iterate through each character in the input word.
    for ch in word:
        # While the current character does not match the expected letter,
        # simulate insertion (advance in expected pattern).
        while ch != expected[pos % 3]:
            insertions += 1        # count missing character insertion
            pos += 1               # move to the next expected position
            
        # If the current character fits, include it in the valid sequence.
        pos += 1
        
    # After processing, if the expected cycle is not complete, add missing letters.
    insertions += (3 - (pos % 3)) % 3
    return insertions

# Example usage:
print(add_min_letters("b"))   # Expected output: 2
print(add_min_letters("aaa")) # Expected output: 6
print(add_min_letters("abc")) # Expected output: 0
← Back to All Questions