Permutation/Combination problems are always a tough nut to crack.
Given a Rock paper scissors game of N turns played by 2 people (round win : 1 point, round draw : 0)
Player 1 sequence has been provided. Player 2 needs to win without playing same move twice in a row.
Find Number of ways to win (with Mod 1000000007 to prevent integer overflow).
(Win condition - Player 2 has more round wins than Player 1)
(R- Rock, P- Paper, S-Scissor)
e.g. 3 rounds - RRR
Player 2 can win by PRP, PSP, RPR
Answer : 3
e.g. 2 rounds - RP
Player 2 can win by PS, RS
(PP not allowed because consecutive same moves cannot be played by Player 2)
Answer : 2
Is it a true Permutation problem or does the no consecutive same moves condition make it more of a DP problem?
(I remember that every Permutation/Combination can be a DP but every DP cannot be a Perm/Comb)
PS - This is not part of any active programming contest.
It was a part of an interview round in past and had a time limit of 30 min.
Bruteforce trying to generate each string would not work.
Total ways to win would be sum of the number of ways to win by 1 round, 2 rounds, ... N rounds.
Without the constraint of no two consecutive moves same, it would be much simpler.
For N round wins - 1 way
For N-1 round wins - N ways (for N-1 wins and 1 draw)
For N-2 round wins - N*N-1 ways (for N-2 wins and 2 draws) + N ways (for N-1 wins and 1 loss)
Ans = (1) + (N) + (N*N-1 + N) ...
But as soon as the constraint arrives, the sequence of Players 1 moves matter.
Now with the constraint
For N round wins - it may not be possible if the player 1 sequence has even 1 character repeated in sequence
e.g. PRR (cannot win 3 rounds)
Was unable to identify how the number of was for each count of round wins would be.