Jobs

Interviews

Discussions

Minimum Additions to Make Valid String

Medium

Asked by:

46 views

Topics:

StringsDynamic Programming

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 <= 50
word consists of letters "a", "b" and "c" only.

Try coding it in LeetCode

Minimum Additions to Make Valid String

Medium

Asked by:

46 views

Topics:

StringsDynamic Programming

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 <= 50
word consists of letters "a", "b" and "c" only.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string contain characters other than 'a', 'b', and 'c'?
Is the input string case-sensitive?
Can the input string be empty or null?
What is the maximum length of the input string?
If there are multiple ways to make the string valid with the minimum number of additions, is any valid solution acceptable?

Brute Force Solution

Approach

The brute force method for making a string valid involves checking every possible combination of additions. We'll explore each position in the string and try inserting 'a', 'b', or 'c' to see if it results in a valid sequence (abc).

Here's how the algorithm would work step-by-step:

Start by considering the original string as is.
Then, imagine inserting 'a', 'b', or 'c' at the very beginning of the string and check if the resulting string is valid.
Next, try inserting 'a', 'b', or 'c' at the second position, and again verify if the resulting string is valid.
Keep repeating this process for every possible position in the string, each time inserting 'a', 'b', or 'c'.
For each new string formed by inserting 'a', 'b', or 'c', check if it contains only the 'abc' sequence repeated any number of times.
If a string is found to be valid, count the number of additions ('a', 'b', or 'c' insertions) made to achieve it.
Repeat all these steps until all the combinations of insertions are considered.
Finally, pick the string that required the least number of additions to become valid. That's the answer.

Code Implementation

def minimum_additions_brute_force(word):
    minimum_additions = float('inf')
    queue = [(word, 0)]

    while queue:
        current_string, additions_count = queue.pop(0)

        if is_valid(current_string):
            minimum_additions = min(minimum_additions, additions_count)
            continue

        # Only explore strings with fewer additions than the current minimum.
        if additions_count >= minimum_additions:
            continue

        for index in range(len(current_string) + 1):
            for char_to_insert in ['a', 'b', 'c']:
                new_string = current_string[:index] + char_to_insert + current_string[index:]
                queue.append((new_string, additions_count + 1))

    return minimum_additions

def is_valid(word):
    #Check if the string consists of repeated "abc" sequences.
    if len(word) % 3 != 0:
        return False

    for index in range(0, len(word), 3):
        if word[index:index + 3] != 'abc':
            return False

    return True

Big(O) Analysis

Time Complexity

O(3^n * n) – The brute force approach involves inserting 'a', 'b', or 'c' at every possible position in the string. This leads to exploring 3 possible insertions at each of the n+1 positions (including before the first character and after the last), resulting in a branching factor of 3 for each position. Therefore, we explore on the order of 3^n different strings. For each of these strings, we need to check if it's a valid 'abc' repetition, which involves iterating through the string of length potentially up to 3n (if we add a lot of characters) to verify its structure. Hence, the time complexity becomes O(3^n * n).

Space Complexity

O(3^N) – The brute force approach described involves exploring every possible combination of 'a', 'b', or 'c' insertions at each position in the string. This leads to a branching factor of 3 for each of the N positions in the input string, where N is the length of the input string. The space complexity arises from the storage of these intermediate strings, each potentially of length up to 2N (in the worst-case scenario, insertions at every original character). Therefore, the number of possible strings to consider grows exponentially, leading to a space complexity of O(3^N).

Optimal Solution

Approach

The goal is to find the fewest characters we need to add to a string to make it composed of only 'abc' subsequences. We can solve this by processing the string one character at a time, greedily completing 'abc' subsequences whenever possible.

Here's how the algorithm would work step-by-step:

Start looking at the string from the beginning.
Keep track of how many of each character ('a', 'b', 'c') we've seen so far in an incomplete 'abc' subsequence.
If we encounter an 'a', we need one more 'b' and 'c' to complete a valid subsequence.
If we encounter a 'b', and we've already seen an 'a' but not a 'b', we now need one more 'c' to complete the subsequence.
If we encounter a 'c', and we've seen both 'a' and 'b' but not 'c' yet, we have successfully completed an 'abc' subsequence, and we can reset our count.
If at any point we see a character out of order (e.g., a 'b' before an 'a'), we can ignore it.
At the end, if we still have an incomplete subsequence (e.g., we've seen 'a' and 'b' but not 'c'), we add the number of missing characters to our count.
The total number of characters added throughout this process will be the minimum additions to make a valid string.

Code Implementation

def min_additions(word): 
    additions_needed = 0
    a_count = 0
    b_count = 0

    for char in word:
        if char == 'a':
            a_count = 1

        elif char == 'b':
            # Only increment if we've already seen 'a'
            if a_count == 1:
                b_count = 1

        elif char == 'c':
            # Only increment if we've already seen 'a' and 'b'
            if a_count == 1 and b_count == 1:
                # Reset counts after completing 'abc'
                a_count = 0
                b_count = 0

    # Add missing characters from incomplete subsequences.
    if a_count == 1 and b_count == 0:
        additions_needed += 2
    elif a_count == 1 and b_count == 1:
        additions_needed += 1
    elif a_count == 0 and b_count == 1:
        additions_needed += 2

    return additions_needed

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string once. For each character in the string, it performs a constant amount of work to update the counts of 'a', 'b', and 'c' encountered. The number of operations is therefore directly proportional to the length of the string, which we denote as n. Thus, the time complexity is O(n).

Space Complexity

O(1) – The algorithm uses a constant number of integer variables to keep track of the counts of 'a', 'b', and 'c' encountered so far. Regardless of the input string's length (N), the number of these counter variables remains fixed. Therefore, the auxiliary space required does not scale with the input size, resulting in constant space complexity.

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 since no additions are needed for an empty string.
Input string with a length of 1 or 2	Handles correctly as the algorithm iterates through and checks for the 'abc' pattern requirements.
String contains characters other than 'a', 'b', or 'c'	Invalid input; either throw an exception or ignore the invalid characters and proceed.
String consisting of only one character ('a', 'b', or 'c') repeated many times.	Calculates the number of 'bc' or 'c' characters needed after each sequence of repeated characters to form 'abc' substrings.
String already valid (consisting of repeating 'abc' sequences).	Return 0 since no additions are needed.
Maximum string length (check for performance bottlenecks)	Iterative solution should scale linearly; consider optimizing further if time limit exceeded due to excessive string length.
String with many 'a's followed by many 'b's, then many 'c's	Ensures each character is added as needed in proper sequence to create substrings of 'abc'.
String with a very unbalanced distribution of 'a', 'b', and 'c'	The algorithm correctly accounts for the necessary character additions regardless of the character frequency.

Null or empty input string

How to Handle:

Return 0 since no additions are needed for an empty string.

Input string with a length of 1 or 2

How to Handle:

Handles correctly as the algorithm iterates through and checks for the 'abc' pattern requirements.

String contains characters other than 'a', 'b', or 'c'

How to Handle:

Invalid input; either throw an exception or ignore the invalid characters and proceed.

String consisting of only one character ('a', 'b', or 'c') repeated many times.

How to Handle:

Calculates the number of 'bc' or 'c' characters needed after each sequence of repeated characters to form 'abc' substrings.

String already valid (consisting of repeating 'abc' sequences).

How to Handle:

Return 0 since no additions are needed.

Maximum string length (check for performance bottlenecks)

How to Handle:

Iterative solution should scale linearly; consider optimizing further if time limit exceeded due to excessive string length.

String with many 'a's followed by many 'b's, then many 'c's

How to Handle:

Ensures each character is added as needed in proper sequence to create substrings of 'abc'.

String with a very unbalanced distribution of 'a', 'b', and 'c'

How to Handle:

The algorithm correctly accounts for the necessary character additions regardless of the character frequency.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string contain characters other than 'a', 'b', and 'c'?
Is the input string case-sensitive?
Can the input string be empty or null?
What is the maximum length of the input string?
If there are multiple ways to make the string valid with the minimum number of additions, is any valid solution acceptable?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start by considering the original string as is.
Then, imagine inserting 'a', 'b', or 'c' at the very beginning of the string and check if the resulting string is valid.
Next, try inserting 'a', 'b', or 'c' at the second position, and again verify if the resulting string is valid.
Keep repeating this process for every possible position in the string, each time inserting 'a', 'b', or 'c'.
For each new string formed by inserting 'a', 'b', or 'c', check if it contains only the 'abc' sequence repeated any number of times.
If a string is found to be valid, count the number of additions ('a', 'b', or 'c' insertions) made to achieve it.
Repeat all these steps until all the combinations of insertions are considered.
Finally, pick the string that required the least number of additions to become valid. That's the answer.

Code Implementation

def minimum_additions_brute_force(word):
    minimum_additions = float('inf')
    queue = [(word, 0)]

    while queue:
        current_string, additions_count = queue.pop(0)

        if is_valid(current_string):
            minimum_additions = min(minimum_additions, additions_count)
            continue

        # Only explore strings with fewer additions than the current minimum.
        if additions_count >= minimum_additions:
            continue

        for index in range(len(current_string) + 1):
            for char_to_insert in ['a', 'b', 'c']:
                new_string = current_string[:index] + char_to_insert + current_string[index:]
                queue.append((new_string, additions_count + 1))

    return minimum_additions

def is_valid(word):
    #Check if the string consists of repeated "abc" sequences.
    if len(word) % 3 != 0:
        return False

    for index in range(0, len(word), 3):
        if word[index:index + 3] != 'abc':
            return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start looking at the string from the beginning.
Keep track of how many of each character ('a', 'b', 'c') we've seen so far in an incomplete 'abc' subsequence.
If we encounter an 'a', we need one more 'b' and 'c' to complete a valid subsequence.
If we encounter a 'b', and we've already seen an 'a' but not a 'b', we now need one more 'c' to complete the subsequence.
If we encounter a 'c', and we've seen both 'a' and 'b' but not 'c' yet, we have successfully completed an 'abc' subsequence, and we can reset our count.
If at any point we see a character out of order (e.g., a 'b' before an 'a'), we can ignore it.
At the end, if we still have an incomplete subsequence (e.g., we've seen 'a' and 'b' but not 'c'), we add the number of missing characters to our count.
The total number of characters added throughout this process will be the minimum additions to make a valid string.

Code Implementation

def min_additions(word): 
    additions_needed = 0
    a_count = 0
    b_count = 0

    for char in word:
        if char == 'a':
            a_count = 1

        elif char == 'b':
            # Only increment if we've already seen 'a'
            if a_count == 1:
                b_count = 1

        elif char == 'c':
            # Only increment if we've already seen 'a' and 'b'
            if a_count == 1 and b_count == 1:
                # Reset counts after completing 'abc'
                a_count = 0
                b_count = 0

    # Add missing characters from incomplete subsequences.
    if a_count == 1 and b_count == 0:
        additions_needed += 2
    elif a_count == 1 and b_count == 1:
        additions_needed += 1
    elif a_count == 0 and b_count == 1:
        additions_needed += 2

    return additions_needed

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return 0 since no additions are needed for an empty string.
Input string with a length of 1 or 2	Handles correctly as the algorithm iterates through and checks for the 'abc' pattern requirements.
String contains characters other than 'a', 'b', or 'c'	Invalid input; either throw an exception or ignore the invalid characters and proceed.
String consisting of only one character ('a', 'b', or 'c') repeated many times.	Calculates the number of 'bc' or 'c' characters needed after each sequence of repeated characters to form 'abc' substrings.
String already valid (consisting of repeating 'abc' sequences).	Return 0 since no additions are needed.
Maximum string length (check for performance bottlenecks)	Iterative solution should scale linearly; consider optimizing further if time limit exceeded due to excessive string length.
String with many 'a's followed by many 'b's, then many 'c's	Ensures each character is added as needed in proper sequence to create substrings of 'abc'.
String with a very unbalanced distribution of 'a', 'b', and 'c'	The algorithm correctly accounts for the necessary character additions regardless of the character frequency.

Null or empty input string

How to Handle:

Return 0 since no additions are needed for an empty string.

Input string with a length of 1 or 2

How to Handle:

Handles correctly as the algorithm iterates through and checks for the 'abc' pattern requirements.

String contains characters other than 'a', 'b', or 'c'

How to Handle:

Invalid input; either throw an exception or ignore the invalid characters and proceed.

String consisting of only one character ('a', 'b', or 'c') repeated many times.

How to Handle:

Calculates the number of 'bc' or 'c' characters needed after each sequence of repeated characters to form 'abc' substrings.

String already valid (consisting of repeating 'abc' sequences).

How to Handle:

Return 0 since no additions are needed.

Maximum string length (check for performance bottlenecks)

How to Handle:

Iterative solution should scale linearly; consider optimizing further if time limit exceeded due to excessive string length.

String with many 'a's followed by many 'b's, then many 'c's

How to Handle:

Ensures each character is added as needed in proper sequence to create substrings of 'abc'.

String with a very unbalanced distribution of 'a', 'b', and 'c'

How to Handle:

The algorithm correctly accounts for the necessary character additions regardless of the character frequency.