DDSA Solutions

2645. Minimum Additions to Make Valid String

MediumView on LeetCode
StringGreedy
Time: O(n)
Space: O(1)

Problem Overview

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

Intuition

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

Algorithm

  1. 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
C#
// 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?

Related Problems