Keep Neighbouring Letters Apart

Medium

Call two lowercase English letters **similar** if they are equal or sit right next to each other in the alphabet (for example c and d, or k and k). You get a string text. One change puts any lowercase letter at any position. Find the smallest number of changes after which no two adjacent letters of the string are similar.

Example 1

text="moon" → 1

The trouble spots are "oo" and "on" (n and o are alphabet neighbours). Replacing the second o, e.g. "moxn", fixes both, so one change is enough.

Example 2

text="bbbb" → 2

For example "bxbx": two changes, and fewer is impossible since pairs (0,1) and (2,3) do not overlap.

Example 3

text="aceg" → 0

Neighbouring letters are already far apart, nothing to change.

Constraints

1 ≤ len(text) ≤ 100
text consists of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy String Dynamic Programming

Similar problems

Brackets With Wildcards Medium Bead String Without Twins Medium Alternate After Rotating Medium Wells Beside the Houses Medium Binary Number Under a Cap Medium

Input

text="moon"

Expected

Run checks the first 3 tests in your browser. Submit checks all 94 tests on the server, hidden ones included.