Question

2645. Minimum Additions to Make Valid String

中文文档

Description

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 "a" 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. 

Solutions

Solution 1: 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)$.

class Solution:
  def addMinimum(self, word: str) -> int:
    s = 'abc'
    ans, n = 0, len(word)
    i = j = 0
    while j < n:
      if word[j] != s[i]:
        ans += 1
      else:
        j += 1
      i = (i + 1) % 3
    if word[-1] != 'c':
      ans += 1 if word[-1] == 'b' else 2
    return ans

class Solution {
  public int addMinimum(String word) {
    String s = "abc";
    int ans = 0, n = word.length();
    for (int i = 0, j = 0; j < n; i = (i + 1) % 3) {
      if (word.charAt(j) != s.charAt(i)) {
        ++ans;
      } else {
        ++j;
      }
    }
    if (word.charAt(n - 1) != 'c') {
      ans += word.charAt(n - 1) == 'b' ? 1 : 2;
    }
    return ans;
  }
}

class Solution {
public:
  int addMinimum(string word) {
    string s = "abc";
    int ans = 0, n = word.size();
    for (int i = 0, j = 0; j < n; i = (i + 1) % 3) {
      if (word[j] != s[i]) {
        ++ans;
      } else {
        ++j;
      }
    }
    if (word[n - 1] != 'c') {
      ans += word[n - 1] == 'b' ? 1 : 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
}

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;
}