Minimum Changes Circular Rock Paper Scissors
Engineers are sitting around a circular table and each engineer chooses one option from Rock, Paper, and Scissors. The choices are represented by the characters 'R', 'P', and 'S'.
Two neighboring engineers tie if they choose the same option. You may change any engineer's choice to either of the other two options. Return the minimum number of engineers whose choices must be changed so that no two adjacent engineers have the same choice.
Since the table is circular, the first and last engineers are also considered adjacent.
Method Signature
Minimum Changes
int minChanges(String choices)
choices contains only 'R', 'P', and 'S'.- Rock-Paper-Scissors winning rules do not matter. Only equal neighboring choices are invalid.
- Returns the minimum number of positions that must be changed.
Input
choices: a string of length n, where choices[i] is the choice made by the engineer at index i in clockwise order.
Output
- Return an integer representing the minimum number of changes required so that every pair of adjacent engineers has different choices.
Constraints
3 ≤ n ≤ 200,000choices[i] ∈ {'R', 'P', 'S'}- The arrangement is circular, so index
0 and index n - 1 are adjacent.
Examples
Example 1
minChanges(choices = "RPSRR")
Output: 1
Explanation: The last 'R' is equal to both its left neighbor and the first engineer's choice because the table is circular. Changing the last choice to 'P' removes all adjacent ties.
Example 2
minChanges(choices = "PPPPPP")
Output: 3
Explanation: One optimal arrangement is "PRPRPR", which changes three engineers and has no equal adjacent choices.
Example 3
minChanges(choices = "RSPRPS")
Output: 0
Explanation: Every adjacent pair already has different choices, including the first and last engineers.