#K33487. Minimum Stone Removals to Avoid Adjacent Duplicates
Minimum Stone Removals to Avoid Adjacent Duplicates
Minimum Stone Removals to Avoid Adjacent Duplicates
You are given a row of n stones, each with a color represented by a character. Your task is to calculate the minimum number of stones to remove so that no two adjacent stones have the same color.
More formally, given a string stones of length n, you need to remove stones such that for every valid index i (1 ≤ i < n), the condition \[ s_i \neq s_{i+1} \] holds true. If there are consecutive stones with the same color, you must remove all but one from each group.
Example: For n = 3 and stones = "RRG", you can remove one of the adjacent 'R's to obtain "RG", which satisfies the condition. Thus, the answer is 1.
inputFormat
The input consists of two lines:
- The first line contains a single integer \( n \) (1 ≤ n ≤ 100), representing the number of stones.
- The second line contains a string of length \( n \) where each character denotes a color of a stone.
You should read input from stdin
.
outputFormat
Output a single integer representing the minimum number of stones that need to be removed so that no two adjacent stones have the same color. Print the result to stdout
.
3
RRG
1
</p>