Paypal VO Coding Interview Question: No Pairs Allowed | String Scan and Minimum Replacements

No Pairs Allowed

Description

For each word in a list of words, if any two adjacent characters are equal, change one of them. Determine the minimum number of substitutions required so that the final string contains no adjacent equal characters.

Example

words = ['add', 'book', 'break']

1. 'add': change one d (1 change)
2. 'book': change the middle o (1 change)
3. 'break': no changes necessary (0 changes)

The return array is [1, 1, 0].

Function Description

Complete the function minimalOperations in the editor below.

minimalOperations has the following parameter(s):

• string words[n]: an array of strings

Returns:

• int[n]: each element i is the minimum substitutions for words[i]

This Paypal VO question asks you to compute, for each word, the minimum number of substitutions needed so that no two adjacent characters are the same. The key idea is to scan each string and count runs of equal consecutive characters; for a run of length L, the minimum replacements is floor(L / 2). Summing this over all runs gives the answer in linear time, which makes the solution simple and efficient.