Interview Questions/Coding/Pair Every Letter

Pair Every Letter

Preview mode. Log in to edit, run, submit, and save progress.

Medium

Pair Every Letter

You are given a lowercase English string. In one move, you may change any character to its previous or next alphabet character. For example, changing 'f' to 'e' costs 1 move, and changing 'f' to 'g' also costs 1 move. Characters cannot move before 'a' or after 'z'. Your goal is to modify the string so that every character has at least one equal neighboring character. For example, in a valid string: - "aa" is valid, - "aabb" is valid, - "aaa" is valid, - "aba" is not valid because the middle character has no equal neighbor. Return the minimum number of moves needed to make the string valid.

Examples

Example 1
Input:
aca
Output:
2

Explanation: Change 'c' to 'a' using 2 moves. The string becomes "aaa", where every character has an equal neighbor.

Approach hint

In the final string, every group of equal letters must have length at least 2.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

solution.cpp