Leetcode 2645: Minimum Additions to Make Valid String
Given a string ‘word’ consisting of letters ‘a’, ‘b’, and ‘c’, you can insert letters ‘a’, ‘b’, or ‘c’ anywhere and as many times as needed. Your task is to determine the minimum number of insertions required to transform ‘word’ into a valid string. A string is considered valid if it can be formed by repeatedly concatenating the string ‘abc’.
Problem
Approach
Steps
Complexity
Input: The input consists of a single string 'word' containing only the characters 'a', 'b', and 'c'.
Example: word = 'ab'
Constraints:
• 1 <= word.length <= 50
• word consists of only the characters 'a', 'b', and 'c'.
Output: Return the minimum number of insertions required to make the string valid, i.e., form 'abc' repeatedly.
Example: Output: 1
Constraints:
• The output should be a non-negative integer representing the minimum number of insertions needed.
Goal: The goal is to determine the number of insertions needed to convert the input string into a valid 'abc' repeated string.
Steps:
• Step 1: Track the expected character sequence ('a', 'b', 'c') as you iterate through the string.
• Step 2: If the character in the string does not match the expected one, count the number of insertions required and update the expected character.
• Step 3: After processing the string, handle any remaining expected characters by inserting them.
Goal: The solution must handle strings of length up to 50 efficiently.
Steps:
• The string must consist only of the characters 'a', 'b', and 'c'.
Assumptions:
• Each string will only contain 'a', 'b', and 'c'.
• The string may not initially form a valid 'abc' repeated pattern.
• Input: Input: word = 'ab'
• Explanation: The string 'ab' is missing 'c' to form 'abc'. So, we need 1 insertion (add 'c') to make the string valid.
• Input: Input: word = 'aab'
• Explanation: The string 'aab' is missing 'c' after the first 'a'. We need to insert 'c' after the second 'a' to make it valid, resulting in 1 insertion.
Approach: The approach is to iterate through the string while keeping track of the expected character ('a', 'b', or 'c'). If the current character does not match the expected one, we insert the required characters to complete the 'abc' pattern.
Observations:
• The string should follow the 'abc' pattern, so we need to ensure the correct sequence of characters is maintained.
• We need to count how many characters need to be inserted to make the string valid.
Steps:
• Step 1: Initialize an 'expected' variable to track the next expected character in the sequence ('a', 'b', or 'c').
• Step 2: Traverse through the string, and for each character, check if it matches the expected character.
• Step 3: If it doesn't match, increment the insertion count and adjust the 'expected' character accordingly.
• Step 4: After traversing the string, account for any remaining required insertions to complete the sequence.
Empty Inputs:
• Empty strings are not allowed as per the problem constraints.
Large Inputs:
• Ensure the solution handles strings close to the upper limit of length 50 efficiently.
Special Values:
• Consider cases where the string is already valid (e.g., 'abc').
Constraints:
• The solution should work efficiently for strings of length up to 50.
int addMinimum(string word) {
int exp = 0, res = 0;
int n = word.size();
for(int i = 0; i < n; i++) {
if(exp == (word[i] - 'a')) {
exp = (exp + 1) % 3;
continue;
}
while(exp != (word[i] - 'a')) {
res++;
exp = (exp + 1) % 3;
}
exp = (exp + 1) % 3;
// cout << i << " " << res << " " << exp << "\n";
}
if(word[n - 1] == 'a') res += 2;
if(word[n - 1] == 'b') res += 1;
return res;
}
1 : Initialization
int addMinimum(string word) {
This line defines the function 'addMinimum', which takes a string 'word' as input and returns an integer value.
2 : Variable Declaration
int exp = 0, res = 0;
Here, 'exp' tracks the expected character ('a' or 'b'), and 'res' counts the number of insertions needed.
3 : Length Calculation
int n = word.size();
This line calculates the length of the input string 'word' and stores it in the variable 'n'.
4 : Loop
for(int i = 0; i < n; i++) {
A loop is initiated to iterate through each character in the string 'word'.
5 : Check Expected Character
if(exp == (word[i] - 'a')) {
This conditional checks if the current character matches the expected character ('a' or 'b').
6 : Update Expected Character
exp = (exp + 1) % 3;
If the character matches, 'exp' is updated to the next expected character in a cyclic manner (0 -> 1 -> 2 -> 0).
7 : Continue to Next Iteration
continue;
If the character matches, the loop moves to the next iteration without performing further actions.
8 : While Loop for Insertions
while(exp != (word[i] - 'a')) {
This 'while' loop runs when the current character does not match the expected character.
9 : Increment Insertions
res++;
If the character doesn't match the expected one, an insertion is counted, and 'res' is incremented.
10 : Update Expected Character Inside While Loop
exp = (exp + 1) % 3;
The expected character is updated after each insertion, cycling through 'a' and 'b'.
11 : Update Expected Character
exp = (exp + 1) % 3;
This updates the expected character after processing each character in the string.
12 : Check Last Character for Insertions
if(word[n - 1] == 'a') res += 2;
If the last character of the string is 'a', two insertions are needed to make the string alternating.
13 : Check Last Character for Insertions
if(word[n - 1] == 'b') res += 1;
If the last character of the string is 'b', one insertion is needed to make the string alternating.
14 : Return Result
return res;
Finally, the function returns the total number of insertions required.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity remains linear in all cases, as we simply iterate through the string once.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is constant, as we only need a few variables to track the state of the expected character and the insertion count.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus