2645. Minimum Additions to Make Valid String LeetCode Solution

In this guide, you will get 2645. Minimum Additions to Make Valid String LeetCode Solution with the best time and space complexity. The solution to Minimum Additions to Make Valid String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Minimum Additions to Make Valid String solution in C++
  4. Minimum Additions to Make Valid String solution in Java
  5. Minimum Additions to Make Valid String solution in Python
  6. Additional Resources
2645. Minimum Additions to Make Valid String LeetCode Solution image

Problem Statement of Minimum Additions to Make Valid String

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.

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n)
See also  3080. Mark Elements on Array by Performing Queries LeetCode Solution

2645. Minimum Additions to Make Valid String LeetCode Solution in C++

class Solution {
 public:
  int addMinimum(string word) {
    const string letters = "abc";
    int ans = 0;
    int i = 0;

    while (i < word.length())
      for (const char c : letters) {
        if (i < word.length() && word[i] == c)
          ++i;
        else
          ++ans;
      }

    return ans;
  }
};
/* code provided by PROGIEZ */

2645. Minimum Additions to Make Valid String LeetCode Solution in Java

class Solution {
  public int addMinimum(String word) {
    final char[] letters = new char[] {'a', 'b', 'c'};
    int ans = 0;
    int i = 0;

    while (i < word.length())
      for (final char c : letters) {
        if (i < word.length() && word.charAt(i) == c)
          ++i;
        else
          ++ans;
      }

    return ans;
  }
};
// code provided by PROGIEZ

2645. Minimum Additions to Make Valid String LeetCode Solution in Python

class Solution:
  def addMinimum(self, word: str) -> int:
    letters = ['a', 'b', 'c']
    ans = 0
    i = 0

    while i < len(word):
      for c in letters:
        if i < len(word) and word[i] == c:
          i += 1
        else:
          ans += 1

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Similar: