IBM Coding Question: Min Insertions to Form 'abc' Problem

You are given a lowercase string s and you may only insert characters (no deletions or replacements) to transform it into a string that is one or more repetitions of the pattern "abc" (i.e., ("abc")^k for some k >= 0). The goal is to compute the minimum number of insertions required.

Key idea: think of the target as a repeating pattern "abc". You can scan s left-to-right while maintaining which character in the pattern you currently expect (a, then b, then c). When s[i] matches the expected pattern character, advance both the input index and the pattern state. When it doesn't match, you must insert the expected pattern character (count++), advance the pattern state, but keep the same input index so you still try to match s[i] against the next expected character. Continue until you exhaust s, then add any remaining insertions to finish the last partial "abc" block.

Interview flow: you'll likely start by explaining this greedy, state-machine approach, then write a two-pointer/one-pass implementation and prove correctness. Discuss time O(n) and O(1) extra space. Expect follow-ups on correctness, handling edge cases (empty string, repeated letters), and variations like allowing deletions or different patterns.

Skills demonstrated: string manipulation, greedy algorithms, two-pointers/state machine reasoning, edge-case handling, and time/space complexity analysis. Practicing this type of question helps in technical screens for backend/SWE roles where concise, linear-time string transforms are common.