Paypal VO 面试真题解析：No Pairs Allowed｜字符串扫描与最少替换

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]

这道 Paypal VO 题目要求你处理一组字符串：对每个单词，统计把相邻相同字符消除所需的最少替换次数。核心观察是，只要扫描字符串并检查相邻字符是否相等，遇到连续重复段时可以用贪心方式每隔一个字符替换一次，因此答案就是每个重复连续段长度除以 2 的向下取整之和。实现时只需线性遍历每个单词，维护当前连续相同字符的长度即可，时间复杂度为 O(总字符数)，适合面试中的快速编码题。