Minimum Additions to Make Valid String solution and explanation
Google
9 more videos on this problem
6375. Minimum Additions to Make Valid String - LEETCODE WEEKLY CONTEST 341 (Logic explained)Joyjit Codes · 6:48 · 1K views
Leetcode Weekly contest 341 - Medium - Minimum Additions to Make Valid StringPrakhar Agrawal · 7:46 · 971 views
2645. Minimum Additions to Make Valid String | LeetCode Weekly Contest 341Deep Tech · 9:33 · 794 views
Leetcode 2645 Minimum Additions to Make Valid StringAlgorithmicIQ · 20:26 · 743 views
Leetcode 2645. Minimum Additions to Make Valid String | Weekly Contest 341 | Leetcode weekly contestOffCampus Phodenge | Aman Chowdhury · 17:25 · 501 views
Minimum Additions to Make Valid String LeetCode Q 2645 !!Parth Arora · 4:58 · 467 views
Minimum Additions to Make Valid String - Leetcode 2645 - PythonAlgorithms Casts · 11:44 · 427 views
2645. Minimum Additions to Make Valid String (Leetcode Medium)Programming Live with Larry · 14:41 · 319 views
LeetCode | 2645. Minimum Additions to Make Valid String | Two PointerCompl3x · 18:20 · 250 views
2645. Minimum Additions to Make Valid String | LeetCode's Weekly Contest 341 | LeetCode MediumDSA Explained · 9:06 · 178 views
The 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.
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 <= 50wordconsists of letters "a", "b" and "c" only.
Approach overview
Problem Overview: You are given a string consisting only of the characters 'a', 'b', and 'c'. A valid string is formed by repeating the sequence "abc" any number of times. The task is to compute the minimum number of characters that must be inserted so the final string becomes a sequence of valid abc groups.
Approach 1: Counter to Validate Each Character in Sequence (Greedy) (Time: O(n), Space: O(1))
Traverse the string while tracking which character in the "abc" sequence you expect next. Think of the valid pattern as a cycle: a → b → c → a. For each character in the input, compare it with the expected character. If it matches, move the expected pointer forward. If it does not match, simulate inserting the missing characters until the expected character aligns with the current one. Each simulated insertion increments the answer. This works because the optimal strategy is always to locally fix the sequence before moving forward. The algorithm processes each character once, making it a classic greedy pattern with constant memory.
Approach 2: Character Position Mapping (Alternative Method) (Time: O(n), Space: O(1))
Map each character to its position in the sequence: a=0, b=1, c=2. Iterate through the string and compare the position of the current character with the previous one. If the sequence moves forward (e.g., a→b or b→c), no insertion is needed. If it jumps backward (for example c→a is fine but b→a is invalid), you add the number of characters required to complete the previous abc group. The number of missing characters can be computed with modular arithmetic on the mapped indices. After processing the entire string, add any remaining characters needed to finish the final abc sequence. This approach treats the string like transitions in a cyclic state machine and is often easier to reason about mathematically.
Both strategies operate in linear time because each character is processed exactly once. They also use constant extra memory since only a few counters or indices are maintained. The logic primarily involves character comparisons and arithmetic on the expected sequence.
Recommended for interviews: The greedy sequence-validation approach is the most intuitive and is typically what interviewers expect. It clearly demonstrates how you track a pattern while scanning a string. The position-mapping method is slightly more mathematical and shows deeper insight into sequence transitions, which can stand out in interviews that emphasize pattern recognition or dynamic programming-style state reasoning.
Approach 1: Using Counter to Validate Each Character in Sequence
Iterate through the string, check each character against positions in the sequence 'abc'. An insertion is needed when a character is missing from its expected position in the sequence.
def min_insertions(word: str) -> int:
count = 0
sequence_index = 0
for c in word:
if c == 'abc'[sequence_index]:
sequence_index = (sequence_index + 1) % 3
else:
count += 3 - sequence_index
sequence_index = 1 if c == 'a' else 0
if sequence_index > 0:
count += 3 - sequence_index
return count
word = 'aaa'
print(min_insertions(word))public class MinInsertions {
public static int minInsertions(String word) {
int count = 0;
int sequenceIndex = 0;
for (char c : word.toCharArray()) {
if (c == "abc".charAt(sequenceIndex)) {
sequenceIndex = (sequenceIndex + 1) % 3;
} else {
count += 3 - sequenceIndex;
sequenceIndex = c == 'a' ? 1 : 0;
}
}
if (sequenceIndex > 0) count += 3 - sequenceIndex;
return count;
}
public static void main(String[] args) {
String word = "aaa";
System.out.println(minInsertions(word));
}
}#include <iostream>
#include <string>
using namespace std;
int minInsertions(string word) {
int count = 0;
int sequence_index = 0;
for (char c : word) {
if (c == "abc"[sequence_index]) {
sequence_index = (sequence_index + 1) % 3;
} else {
count += 3 - sequence_index;
sequence_index = (c == 'a' ? 1 : 0);
}
}
if (sequence_index > 0) count += (3 - sequence_index);
return count;
}
int main() {
string word = "aaa";
cout << minInsertions(word) << endl;
return 0;
}function minInsertions(word) {
let count = 0;
let sequenceIndex = 0;
for (let c of word) {
if (c === 'abc'[sequenceIndex]) {
sequenceIndex = (sequenceIndex + 1) % 3;
} else {
count += 3 - sequenceIndex;
sequenceIndex = c === 'a' ? 1 : 0;
}
}
if (sequenceIndex > 0) count += 3 - sequenceIndex;
return count;
}
let word = 'aaa';
console.log(minInsertions(word));#include <stdio.h>
#include <string.h>
int minInsertions(char * word) {
int len = strlen(word);
int count = 0; // Minimum insertions needed
int sequence_index = 0; // Tracks position in 'abc'
for (int i = 0; i < len; i++) {
// Match current character to the expected sequence
if (word[i] == "abc"[sequence_index]) {
sequence_index = (sequence_index + 1) % 3;
} else {
// If mismatch, calculate how many inserts are needed
count += (3 - sequence_index);
sequence_index = 1; // start again from 'b' once 'a' is placed.
}
}
// Add remaining characters if sequence is not complete
if (sequence_index > 0) count += (3 - sequence_index);
return count;
}
int main() {
char word[] = "aaa";
printf("%d\n", minInsertions(word));
return 0;
}using System;
class Program {
static int MinInsertions(string word) {
int count = 0;
int sequenceIndex = 0;
foreach (char c in word) {
if (c == "abc"[sequenceIndex]) {
sequenceIndex = (sequenceIndex + 1) % 3;
} else {
count += 3 - sequenceIndex;
sequenceIndex = c == 'a' ? 1 : 0;
}
}
if (sequenceIndex > 0) count += 3 - sequenceIndex;
return count;
}
static void Main() {
string word = "aaa";
Console.WriteLine(MinInsertions(word));
}
}This Python function iterates through the string and counts how many additional characters are needed to complete 'abc' sequences whenever there is a character mismatch.
Time Complexity: O(n), with n being the length of the string.
Space Complexity: O(1), constant space required.
Approach 2: Using Character Position Mapping (Alternative Method)
In this method, maintain counters for how many 'a's, 'b's, and 'c's have been seen, ensuring a valid pattern by correcting whenever necessary.
def min_additions(word: str) -> int:
a_count = b_count = c_count = additions = 0
for c in word:
if c == 'a':
a_count += 1
elif c == 'b':
b_count += 1
elif c == 'c':
c_count += 1
if b_count > a_count:
additions += b_count - a_count
a_count = b_count
if c_count > b_count:
additions += c_count - b_count
b_count = c_count
if a_count > b_count and b_count == c_count:
additions += a_count - b_count
b_count = a_count
c_count = b_count
additions += (a_count - b_count) * 2 + (b_count - c_count)
return additions
word = 'aaa'
print(min_additions(word))public class MinAdditionsExample {
public static int minAdditions(String word) {
int a_count = 0, b_count = 0, c_count = 0, additions = 0;
for (char c : word.toCharArray()) {
if (c == 'a') a_count++;
else if (c == 'b') b_count++;
else if (c == 'c') c_count++;
if (b_count > a_count) {
additions += (b_count - a_count);
a_count = b_count;
}
if (c_count > b_count) {
additions += (c_count - b_count);
b_count = c_count;
}
if (a_count > b_count && b_count == c_count) {
additions += (a_count - b_count);
b_count = a_count;
c_count = b_count;
}
}
additions += (a_count - b_count) * 2 + (b_count - c_count);
return additions;
}
public static void main(String[] args) {
String word = "aaa";
System.out.println(minAdditions(word));
}
}#include <iostream>
#include <string>
using namespace std;
int minAdditions(string word) {
int a_count = 0, b_count = 0, c_count = 0, additions = 0;
for (char c : word) {
if (c == 'a') a_count++;
else if (c == 'b') b_count++;
else if (c == 'c') c_count++;
if (b_count > a_count) {
additions += (b_count - a_count);
a_count = b_count;
}
if (c_count > b_count) {
additions += (c_count - b_count);
b_count = c_count;
}
if (a_count > b_count && b_count == c_count) {
additions += (a_count - b_count);
b_count = a_count;
c_count = b_count;
}
}
additions += (a_count - b_count) * 2 + (b_count - c_count);
return additions;
}
int main() {
string word = "aaa";
cout << minAdditions(word) << endl;
return 0;
}function minAdditions(word) {
let a_count = 0, b_count = 0, c_count = 0, additions = 0;
for (let c of word) {
if (c === 'a') a_count++;
else if (c === 'b') b_count++;
else if (c === 'c') c_count++;
if (b_count > a_count) {
additions += (b_count - a_count);
a_count = b_count;
}
if (c_count > b_count) {
additions += (c_count - b_count);
b_count = c_count;
}
if (a_count > b_count && b_count === c_count) {
additions += (a_count - b_count);
b_count = a_count;
c_count = b_count;
}
}
additions += (a_count - b_count) * 2 + (b_count - c_count);
return additions;
}
let word = 'aaa';
console.log(minAdditions(word));#include <stdio.h>
#include <string.h>
int minAdditions(char * word) {
int a_count = 0, b_count = 0, c_count = 0, additions = 0;
for (int i = 0; word[i] != '\0'; i++) {
if (word[i] == 'a') a_count++;
else if (word[i] == 'b') b_count++;
else if (word[i] == 'c') c_count++;
if (b_count > a_count) {
additions += b_count - a_count;
a_count = b_count;
}
if (c_count > b_count) {
additions += c_count - b_count;
b_count = c_count;
}
if (a_count > b_count && b_count == c_count) {
additions += a_count - b_count;
b_count = a_count;
c_count = b_count;
}
}
additions += (a_count - b_count) * 2 + (b_count - c_count);
return additions;
}
int main() {
char word[] = "aaa";
printf("%d\n", minAdditions(word));
return 0;
}using System;
class Solution {
static int MinAdditions(string word) {
int aCount = 0, bCount = 0, cCount = 0, additions = 0;
foreach (char c in word) {
if (c == 'a') aCount++;
else if (c == 'b') bCount++;
else if (c == 'c') cCount++;
if (bCount > aCount) {
additions += bCount - aCount;
aCount = bCount;
}
if (cCount > bCount) {
additions += cCount - bCount;
bCount = cCount;
}
if (aCount > bCount && bCount == cCount) {
additions += aCount - bCount;
bCount = aCount;
cCount = bCount;
}
}
additions += (aCount - bCount) * 2 + (bCount - cCount);
return additions;
}
static void Main() {
string word = "aaa";
Console.WriteLine(MinAdditions(word));
}
}This Python solution is designed to keep counts of each character and corrects any deficits or exceeds to maintain the required 'abc' pattern by calculating needed insertions.
Time Complexity: O(n), looping through the string length.
Space Complexity: O(1).
Approach 3: Greedy + Two Pointers
We define the string s as "abc", and use pointers i and j to point to s and word respectively.
If word[j] neq s[i], we need to insert s[i], and we add 1 to the answer; otherwise, it means that word[j] can match with s[i], and we move j one step to the right.
Then, we move i one step to the right, i.e., i = (i + 1) bmod 3. We continue the above operations until j reaches the end of the string word.
Finally, we check whether the last character of word is 'b' or 'a'. If it is, we need to insert 'c' or 'bc', and we add 1 or 2 to the answer and return it.
The time complexity is O(n), where n is the length of the string word. The space complexity is O(1).
function addMinimum(word: string): number {
const s: string = 'abc';
let ans: number = 0;
const n: number = word.length;
for (let i = 0, j = 0; j < n; i = (i + 1) % 3) {
if (word[j] !== s[i]) {
++ans;
} else {
++j;
}
}
if (word[n - 1] === 'b') {
++ans;
} else if (word[n - 1] === 'a') {
ans += 2;
}
return ans;
}func addMinimum(word string) (ans int) {
s := "abc"
n := len(word)
for i, j := 0, 0; j < n; i = (i + 1) % 3 {
if word[j] != s[i] {
ans++
} else {
j++
}
}
if word[n-1] == 'b' {
ans++
} else if word[n-1] == 'a' {
ans += 2
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using Counter to Validate Each Character in Sequence | Time Complexity: O(n), with n being the length of the string. |
| Using Character Position Mapping (Alternative Method) | Time Complexity: O(n), looping through the string length. |
| Greedy + Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counter to Validate Each Character in Sequence (Greedy) | O(n) | O(1) | Best general solution. Easy to implement during interviews and clearly follows the expected abc pattern. |
| Character Position Mapping | O(n) | O(1) | Useful when reasoning about cyclic sequences using index math or modular transitions. |
Frequently asked questions
Is Minimum Additions to Make Valid String easy or hard?
The problem is rated Medium on LeetCode because it requires recognizing the repeating "abc" structure and handling sequence transitions correctly. The implementation itself is straightforward once you identify the greedy pattern validation strategy.
How to solve Minimum Additions to Make Valid String in O(n)?
Scan the string while maintaining the expected character in the repeating sequence a → b → c. When the current character does not match the expected one, simulate inserting the missing characters until the sequence aligns. Continue processing the string and add remaining characters at the end to complete the final "abc" group.
What is the best approach for Minimum Additions to Make Valid String?
The greedy sequence-validation approach is the most practical solution. You iterate through the string while tracking the expected character in the repeating "abc" sequence and count how many characters must be inserted when the order breaks. This runs in O(n) time with O(1) space and is typically the approach interviewers expect.
What data structure is used in Minimum Additions to Make Valid String?
The solution primarily relies on simple counters and character comparisons rather than complex data structures. Some implementations model the sequence using indices or modular arithmetic, while others track the expected character in the "abc" pattern.
What is the time complexity of Minimum Additions to Make Valid String?
The optimal solution runs in O(n) time where n is the length of the input string. Each character is processed exactly once while validating the expected "abc" order. The space complexity is O(1) because only a few counters or indices are stored.
Minimum Additions to Make Valid String Python or Java solution approach?
Both Python and Java implementations typically follow the greedy pattern-tracking approach. You iterate through the string, compare each character with the expected position in "abc", and increment a counter whenever characters must be inserted. The logic remains O(n) time and O(1) space across languages.
Is Minimum Additions to Make Valid String asked at Google, Amazon, or Meta?
String pattern validation and greedy sequence problems like this commonly appear in interviews at large tech companies including Google, Amazon, and Meta. While the exact problem may vary, the underlying idea of validating ordered character patterns in linear time is a common interview theme.