2645. Minimum Additions to Make Valid String
Problem Description
The given problem presents a scenario where you are working with strings and the goal is to make the given input string word
valid by inserting additional letters. The valid form of the string is defined as one that can be generated by repeatedly concatenating the sub-string "abc". For example, "abcabc" and "abc" are valid strings, but "abbc" and "ac" are not.
To solve this problem, you have to identify the minimum number of letters that need to be inserted into the given string word
to make it valid. You are permitted to insert the letters "a", "b", or "c".
To clarify, if the word
is "aabcbc", you would need to insert "b" before the first "a" to make it "abcabc", which is a valid string. So, the output in this case would be 1, as only one insertion is necessary.
Intuition
The intuition behind the solution revolves around tracking the expected sequence of the characters "a", "b", and "c". As the valid string should have "abc" repeating, we can impose this sequence on the given word
and count the number of deviations from it.
The core idea is to iterate through the given word
and check if the current character matches the expected character in the sequence "abc". If it doesn't match, this means we would have to insert the expected character, and thus we increment our count of insertions. We continue to do this throughout the string, tracking whether we are expecting an "a", "b", or "c" at each position and incrementing the insertion count each time the actual character does not match the expected one. By the end of this process, we will have a count that represents the minimum insertions required to make the string valid.
In special cases, such as the end of the string, we may need to add extra characters depending on what the last character is. If it is not "c", we conclude the sequence with the necessary characters to complete the "abc" pattern.
For instance, if the last processed character of the word was "a", we need to insert "bc" to end the string with a complete "abc" pattern; thus we would add 2 to our count. Similarly, if it was "b", we only need to insert "c", adding 1 to our count. Hence, the insertion count after processing the full string gives us the answer.
Learn more about Stack, Greedy and Dynamic Programming patterns.
Solution Approach
The solution approach leverages a straightforward iteration pattern along with a simple modulo operation to track the expected sequence of characters, "a", "b", and "c". Here, we detail the steps and logic used in the provided solution code. The solution does not depend on complicated data structures or algorithms; instead, it uses basic control structures.
-
Initialize two pointers
i
(to track the sequence "abc") andj
(to iterate through the givenword
), as well as a variableans
to keep count of the minimum insertions required. -
i
is used to reference the index of the characters in the strings
, which is "abc". It cycles through 0, 1, 2, and then back to 0, by using the expression(i + 1) % 3
. -
Start iterating through the given
word
using thej
pointer, and compare each character inword
at indexj
with the character ins
at indexi
. -
If the characters do not match (
word[j] != s[i]
), it means an insertion is needed to maintain the valid "abc" pattern, so incrementans
. -
When the characters do match (
word[j] == s[i]
), move to the next character inword
by incrementingj
. Thei
pointer gets updated to the expected next character in the sequence regardless of whether there was a match or not, to model the fact that an insertion was made or a correct character was observed. -
After the main loop, if the last character of
word
is not 'c', it means that the currentabc
sequence hasn't been completed. Hence, we need to add characters to complete the sequence. If the last character is 'b', only one more character ('c') is needed, else if it's 'a', two characters ('bc') are required. -
Finally, the function returns the value of
ans
, which after these steps, contains the minimum number of insertions required to make theword
a valid string.
An important aspect to note is the simplicity of the solution. There is no use of complex data structures; the entire logic revolves around two pointers and comparisons, making the approach elegant and efficient with a time complexity of O(n), where n is the length of the word
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's apply the solution approach to a small example, where the input word
is "abab".
-
Initialize
i
to point to the start of the sequence, andj
to point at the first character ofword
.ans
is initialized to 0.i
points to 'a' in the sequence "abc".j
points to 'a' inword
.ans
is 0.
-
Iterate through each character in
word
:- Compare
word[j]
('a') withs[i]
('a'). They match, so no insertion is needed. Incrementi
using(i + 1) % 3
, which setsi
to point to 'b'. - Move to the next character in
word
('b'),j
becomes 1. - Compare
word[j]
('b') withs[i]
('b'). They match again, so incrementi
to point to 'c'. - Move to next character in
word
('a'),j
becomes 2. - Compare
word[j]
('a') withs[i]
('c'). They do not match, so an insertion is needed. Incrementans
to 1, and updatei
to point to 'a'. - As we haven't advanced
j
due to the non-match, compareword[j]
('a') withs[i]
('a') again. They match, so now incrementi
(pointing to 'b'), and incrementj
to point to the last character inword
('b'). - Compare
word[j]
('b') withs[i]
('b'). They match, so incrementi
to point to 'c'. - Since we've reached the end of
word
, we look at the last character ('b'). It is not 'c', so we conclude the sequence needs a 'c'. Incrementans
to 2.
- Compare
-
By the end of the iteration,
ans
indicates that we need 2 insertions forword
to become "abcabc", which is a valid string by the problem definition.
Solution Implementation
1class Solution:
2 def add_minimum(self, word: str) -> int:
3 # Pattern to be matched
4 pattern = 'abc'
5
6 # Initialize counter for additional characters and the length of the word
7 additional_chars = 0
8 word_length = len(word)
9
10 # Initialize pointers for word and pattern
11 pattern_index = 0
12 word_index = 0
13
14 # Iterate through the word
15 while word_index < word_length:
16 # If the current character does not match the pattern character
17 if word[word_index] != pattern[pattern_index]:
18 # Increment the counter for additional characters
19 additional_chars += 1
20 else:
21 # Move to the next character in the word if there is a match
22 word_index += 1
23
24 # Move to the next character in the pattern, wrapping around as needed
25 pattern_index = (pattern_index + 1) % 3
26
27 # After the last character, ensure the word ends with 'c'
28 # If the word ends with 'b', only 1 additional character ('c') is needed
29 # If the word ends with 'a', 2 additional characters ('bc') are needed
30 if word[-1] != 'c':
31 additional_chars += 1 if word[-1] == 'b' else 2
32
33 # Return the total number of additional characters needed
34 return additional_chars
35
1class Solution {
2 // Method to calculate the minimum number of characters to add
3 public int addMinimum(String word) {
4 // Reference string to compare with
5 String reference = "abc";
6 // Initialize the count of additional characters
7 int count = 0;
8 // Length of the input word
9 int wordLength = word.length();
10
11 // Loop through the word and reference in synchronization
12 for (int refIndex = 0, wordIndex = 0; wordIndex < wordLength; refIndex = (refIndex + 1) % 3) {
13 // If characters do not match, increment the count
14 if (word.charAt(wordIndex) != reference.charAt(refIndex)) {
15 count++;
16 } else {
17 // If characters match, move to the next character in word
18 wordIndex++;
19 }
20 }
21
22 // After processing the main loops, ensure the last character of 'word' is 'c'
23 if (word.charAt(wordLength - 1) != 'c') {
24 // If the last character is 'b', only one character ('c') needs to be added
25 count += word.charAt(wordLength - 1) == 'b' ? 1 : 2;
26 // If the last character is not 'b' (thus it must be 'a'), two characters ('b' and 'c') need to be added
27 }
28
29 // Return the total number of characters that need to be added
30 return count;
31 }
32}
33
1class Solution {
2public:
3 int addMinimum(string word) {
4 // The pattern we want to follow is "abc". We'll iterate through the characters
5 // of the input word and check their alignment with this pattern.
6 string pattern = "abc";
7
8 int modifications = 0; // Count of modifications required to align with the pattern.
9 int wordLength = word.size(); // The length of the input word.
10
11 // Iterate through the input word, using 'i' for the pattern index and 'j' for the word index.
12 for (int i = 0, j = 0; j < wordLength; i = (i + 1) % 3) {
13 // If the current character in the word does not match the current character in the pattern.
14 if (word[j] != pattern[i]) {
15 // We need to perform a modification (increment the counter)
16 ++modifications;
17 } else {
18 // If it matches, we move to the next character in the word.
19 ++j;
20 }
21 }
22
23 // After iterating through the word, we need to ensure the last character matches the pattern.
24 // If the last character is not 'c' we need additional modifications:
25 // If it's 'b', we need to add 'c' so just 1 modification.
26 // If it's 'a' or any other character, we need to add 'bc' so 2 modifications.
27 if (word[wordLength - 1] != 'c') {
28 modifications += (word[wordLength - 1] == 'b' ? 1 : 2);
29 }
30
31 // Return the total number of modifications required.
32 return modifications;
33 }
34};
35
1// This function takes a string "word" and calculates the minimum number of
2// characters that need to be added to make sure that no 'a', 'b', or 'c' is
3// immediately followed by the identical character and the sequence 'abc' is not
4// present.
5function addMinimum(word: string): number {
6 // Define a sequence 'abc' to be used for comparison
7 const sequence: string = 'abc';
8 let additionsNeeded: number = 0; // Counter for the number of additions needed
9 const wordLength: number = word.length; // Length of the input word
10
11 // Loop through the input word and the sequence in parallel until the
12 // end of the word is reached.
13 for (let seqIndex = 0, wordIndex = 0; wordIndex < wordLength; seqIndex = (seqIndex + 1) % 3) {
14 if (word[wordIndex] !== sequence[seqIndex]) {
15 // Increment additionsNeeded when the characters don't match
16 additionsNeeded++;
17 } else {
18 // Move to the next character in the word if there is a match
19 wordIndex++;
20 }
21 }
22
23 // After processing the entire word, if the word ends with 'b', 'c'
24 // needs to be added. If it ends with 'a', both 'b' and 'c' need to be
25 // added to avoid creating the sequence 'abc' or having identical
26 // characters next to each other.
27 if (word[wordLength - 1] === 'b') {
28 additionsNeeded++;
29 } else if (word[wordLength - 1] === 'a') {
30 additionsNeeded += 2;
31 }
32
33 // Return the total number of additions needed
34 return additionsNeeded;
35}
36
Time and Space Complexity
The time complexity of the addMinimum
function is O(n)
, where n
is the length of the input string word
. The function contains a single while loop that iterates over each character of the word exactly once. The operations inside the loop have a constant cost, as they involve only basic arithmetic and comparisons. The final check after the loop is also a constant time operation.
The space complexity of the function is O(1)
. The function uses a finite number of integer variables (ans
, n
, i
, j
) and a constant string s
, with no dependence on the size of the input. Therefore, the amount of space used does not scale with n
, and it stays constant no matter how large the input string is.
Learn more about how to find time and space complexity quickly using problem constraints.
Which type of traversal does breadth first search do?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution