Minimum Additions to Make Valid String - Practice Coding Problems

Minimum Additions to Make Valid String - 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 that word becomes valid.

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

Input & Output

Example 1 — Single Character

$ Input: word = "b"

› Output: 2

💡 Note: Insert 'a' before 'b' and 'c' after 'b' to get 'abc'. Total insertions: 2

Example 2 — Partial Pattern

$ Input: word = "aaa"

› Output: 6

💡 Note: Each 'a' needs 'bc' to complete 'abc'. Three 'a's need 3×2 = 6 insertions total

Example 3 — Already Valid

$ Input: word = "abc"

› Output: 0

💡 Note: String is already valid, no insertions needed

Constraints

1 ≤ word.length ≤ 50
word consists only of letters 'a', 'b', and 'c'

Visualization

Tap to expand

Understanding the Visualization

Input

String 'b' needs to be part of valid 'abc' pattern

Analysis

Track what each character needs to form complete 'abc'

Output

Minimum insertions needed: 2 (add 'a' and 'c')

Key Takeaway

🎯 Key Insight: Track pending characters that need their ABC pattern completed

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is to track pending characters that need completion. Use counters for 'a's waiting for 'b' and 'b's waiting for 'c'. Best approach is Greedy State Machine with Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy State Machine	O(n)	O(1)	Track pending 'a's and 'b's that need their completions
Stack-Based Simulation	O(n)	O(n)	Use stack to simulate the ABC pattern matching process
Brute Force with Recursion	O(4ⁿ)	O(n)	Try all possible ways to insert letters and find minimum

Greedy State Machine — Algorithm Steps

Initialize counters for pending 'a's and 'b's
For each character: match with pending or increment counter
If 'c' appears without pending 'b', need to insert 'a' and 'b'
At end, complete all pending 'a's and 'b's

Visualization

Tap to expand

Step-by-Step Walkthrough

Process 'b'

No pending 'a', so insert 'a', now have pending 'b'

End of String

Pending 'b' needs 'c' to complete

Total Insertions

1 (for 'a') + 1 (for 'c') = 2 insertions

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

int solution(char* word) {
    int a = 0;  // Count of 'a's waiting for 'b'
    int b = 0;  // Count of 'b's waiting for 'c'
    int insertions = 0;
    int len = strlen(word);
    
    for (int i = 0; i < len; i++) {
        char c = word[i];
        if (c == 'a') {
            a++;
        } else if (c == 'b') {
            if (a > 0) {
                a--;
                b++;
            } else {
                // Need to insert 'a' before this 'b'
                insertions++;
                b++;
            }
        } else if (c == 'c') {
            if (b > 0) {
                b--;
            } else {
                // Need to insert 'a' and 'b' before this 'c'
                insertions += 2;
            }
        }
    }
    
    // Complete remaining 'a's (each needs 'bc')
    insertions += 2 * a;
    // Complete remaining 'b's (each needs 'c')
    insertions += b;
    
    return insertions;
}

int main() {
    char word[1000];
    fgets(word, sizeof(word), stdin);
    word[strcspn(word, "\n")] = 0;
    
    int result = solution(word);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string with constant work per character

✓ Linear Growth

Space Complexity

O(1)

Only using three integer variables for counting

✓ Linear Space

23.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy State Machine — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler