minimum-additions-to-make-valid-string

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given a string <code>word</code> to which you can insert letters &quot;a&quot;, &quot;b&quot; or &quot;c&quot; anywhere and any number of times, return the minimum number of letters that must be inserted so that <code>word</code> becomes valid.

A string is called valid if it can be formed by concatenating the string &quot;abc&quot; several times.

&nbsp;
Example 1:

<pre>
Input: word = &quot;b&quot;
Output: 2
Explanation: Insert the letter &quot;a&quot; right before &quot;b&quot;, and the letter &quot;c&quot; right next to &quot;b&quot; to obtain the valid string &quot;abc&quot;.
</pre>

Example 2:

<pre>
Input: word = &quot;aaa&quot;
Output: 6
Explanation: Insert letters &quot;b&quot; and &quot;c&quot; next to each &quot;a&quot; to obtain the valid string &quot;abcabcabc&quot;.
</pre>

Example 3:

<pre>
Input: word = &quot;abc&quot;
Output: 0
Explanation: word is already valid. No modifications are needed. 
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= word.length &lt;= 50</code></li>
	<li><code>word</code> consists of letters &quot;a&quot;, &quot;b&quot;&nbsp;and &quot;c&quot; only.&nbsp;</li>
</ul>

addMinimum

Minimum Additions to Make Valid String

Merge Strings Alternately

merge-strings-alternately

交替合并字符串

Stack

Greedy

String

Dynamic Programming

给你一个字符串 <code>word</code> ，你可以向其中任何位置插入 "a"、"b" 或 "c" 任意次，返回使 <code>word</code> 有效 需要插入的最少字母数。

如果字符串可以由 "abc" 串联多次得到，则认为该字符串 有效 。

&nbsp;

示例 1：

<pre>输入：word = "b"
输出：2
解释：在 "b" 之前插入 "a" ，在 "b" 之后插入 "c" 可以得到有效字符串 "abc" 。
</pre>

示例 2：

<pre>输入：word = "aaa"
输出：6
解释：在每个 "a" 之后依次插入 "b" 和 "c" 可以得到有效字符串 "abcabcabc" 。
</pre>

示例 3：

<pre>输入：word = "abc"
输出：0
解释：word 已经是有效字符串，不需要进行修改。 
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= word.length &lt;= 50</code></li>
	<li><code>word</code> 仅由字母 "a"、"b" 和 "c" 组成。</li>
</ul>