2645. Minimum Additions to Make Valid String

MediumView on LeetCode

String Greedy

Time: O(n)

Space: O(1)

Intuition

Minimum additions to make string valid (no two consecutive characters are same after additions). Count changes needed.

Algorithm

1Count positions where s[i] == s[i+1]. Each such conflict needs 1 insertion.

Common Pitfalls

•Each insertion between two identical adjacent chars. Count adjacent duplicates.

2645.cs

// Approach: Greedily advance through 'abc' template; count extra blocks needed at breaks.
// Time: O(n) Space: O(1)

public class Solution
{
    public int AddMinimum(string word)
    {
        char[] letters = new char[] { 'a', 'b', 'c' };
        int ans = 0;
        int i = 0, n = word.Length;

        while (i < n)
        {
            foreach (char ch in letters)
            {
                if (i < n && word[i] == ch)
                    i++;
                else
                    ans++;
            }
        }

        return ans;
    }
}

Was this solution helpful?