Minimum Additions to Make Valid String

medium string greedy two pointers

Problem

You are given a string word made only of the letters "a", "b", "c". You may insert any of these letters anywhere, any number of times. A string is valid if it equals one or more copies of "abc" joined together ("abc", "abcabc", …). Return the minimum number of letters you must insert to make word valid.

Inputword = "b"

Output2

Insert "a" before "b" and "c" after it to get "abc", so 2 insertions are needed.

word (letters a, b, c)

def addMinimum(word):
    abc = "abc"
    res = 0          # letters we must insert
    j = 0            # pointer into the cyclic "abc" pattern
    for ch in word:
        # insert pattern letters until abc[j] lines up with ch
        while abc[j] != ch:
            res += 1
            j = (j + 1) % 3
        # ch matches abc[j]; consume it and advance
        j = (j + 1) % 3
    # if we stopped mid-block, pad the remaining letters of "abc"
    if j != 0:
        res += 3 - j
    return res

function addMinimum(word) {
  const abc = "abc";
  let res = 0;          // letters we must insert
  let j = 0;            // pointer into the cyclic "abc" pattern
  for (const ch of word) {
    // insert pattern letters until abc[j] lines up with ch
    while (abc[j] !== ch) {
      res += 1;
      j = (j + 1) % 3;
    }
    // ch matches abc[j]; consume it and advance
    j = (j + 1) % 3;
  }
  // if we stopped mid-block, pad the remaining letters of "abc"
  if (j !== 0) res += 3 - j;
  return res;
}

int addMinimum(String word) {
    String abc = "abc";
    int res = 0;          // letters we must insert
    int j = 0;            // pointer into the cyclic "abc" pattern
    for (char ch : word.toCharArray()) {
        // insert pattern letters until abc[j] lines up with ch
        while (abc.charAt(j) != ch) {
            res += 1;
            j = (j + 1) % 3;
        }
        // ch matches abc[j]; consume it and advance
        j = (j + 1) % 3;
    }
    // if we stopped mid-block, pad the remaining letters of "abc"
    if (j != 0) res += 3 - j;
    return res;
}

int addMinimum(string word) {
    string abc = "abc";
    int res = 0;          // letters we must insert
    int j = 0;            // pointer into the cyclic "abc" pattern
    for (char ch : word) {
        // insert pattern letters until abc[j] lines up with ch
        while (abc[j] != ch) {
            res += 1;
            j = (j + 1) % 3;
        }
        // ch matches abc[j]; consume it and advance
        j = (j + 1) % 3;
    }
    // if we stopped mid-block, pad the remaining letters of "abc"
    if (j != 0) res += 3 - j;
    return res;
}

Explanation

A valid string is just the block "abc" repeated. So we can imagine laying down copies of "abc" and slotting the letters of word into the right positions, inserting whatever is missing.

We keep a single pointer j that cycles through positions 0,1,2 of the pattern "abc" (so abc[0]='a', abc[1]='b', abc[2]='c', then back to 'a'). For each character ch of word we ask: does the pattern position we are at equal ch?

If not, the only way to keep things valid is to insert the pattern letter sitting at j, count it in res, and advance j. We repeat until abc[j] finally equals ch. Then ch fits exactly, so we consume it by advancing j once more.

After scanning every character, j tells us how far we are into the current "abc" block. If j != 0 we are mid-block, so we must pad the remaining 3 - j letters to close it off.

Example: word = "aaa". Each 'a' matches at j=0 and advances j to 1; to reach the next 'a' we insert 'b' and 'c' (2 each), and at the end we pad "bc" again, totalling 6.

Time: O(n) Space: O(1)