Game theory optimised solution help

[mnnsa]

Given a string colors, where each character is either white or black, Wendy and Bob play a game to manipulate this string as follows:
• They perform moves alternatively in turns and Wendy makes the first move.

• In a single move, Wendy can remove from the string any white character that has exactly 2 white neighbors.

• Similarly, in a single move, Bob can remove from string any black character that has exactly 2 black neighbors.

• When a character is removed, the strings shrink itself, so if a character Y had neighbors X and Z on its left and right respectively before the move, after the move is made, X and Z become each other's neighbors.

• The first player who cannot perform a move loses the game. For example, if the colors string is wwwbb, with the first move Wendy will change it to wwbb, and Bob can no longer perform a move. Determine who has a winning strategy assuming that both Wendy and Bob play optimally



ANY BETTER OPTIMISED APPROACH THAN MY APPROACH PLEASE SUGGEST

#include <iostream>
using namespace std;
string s="wwwbb";
int main() {
	// your code goes here
	int cnt=0;
	restart:    
	
	//int precnt;
	for(int i=1;i<s.size()-1;i++)
	{
	//	precnt=cnt;
	char b;
	if(cnt==0)
	 b='w';
	else
	 b='b';
	
		//cout<<b;	
		if(s[i]==b && s[i-1]==b && s[i+1]==b)
		{//cout<<"i  "<<i<<endl;
			//cout<<i<<"bbbbbb"
		
		cnt=!cnt;
		 //cout<<s<<endl;
		//cout<<"i"<<i<<endl;
		//cout<<s[i]<<endl;
		 s.erase(i,1);  
		//cout<<s;
		//		 i=1;
		
			  goto restart;    
		}
		else if(s.size()==2)
		{
			//cout<<!cnt;
		if(!cnt==0)
		cout<<"wendy wins"<<endl;
		else
		cout<<"bob wins"<<endl;
			
		}
		else if(i==s.size()-2)
		{//cout<<s<<endl;
			//cout<<!cnt;
				if(!cnt==0)
		cout<<"wendy wins"<<endl;
		else
		cout<<"bob wins"<<endl;
			break;
		
		}
		
	}
	return 0;
}

[salem c]

Before this is a programming problem, it's a math problem.

There are two kinds of solution.

The first is where people come along and simply write code to mechanically perform the steps described in the algorithm. This works for simple test cases, but ends up with either Time Limit Exceeded (TLE) or Memory Limit Exceeded (MLE) when they present their 'solution' to the online judge.

Then there are the second set of people who write out a whole bunch of test cases on paper, try to solve it manually to get a grasp of the real meaning of the problem, and in doing so, spot exploitable patterns that solve the problem far more efficiently than "try all the combinations".

[jonnin]

they have the same strategy, and they play optimally. That means that the winner is simply determined by the string itself, not the strategy, making the question meaningless?

[dutch]

Looks like a simple counting problem.

[mnnsa]

please help with optimal approach

[salem c]

Just by inspection, figure out who wins.

wwwwbb
wwwwbbb
wwwwbbbb
wwwwbbbbb

Answer the question, when does black start winning, and what actually changed for that to be possible.

[coder777]

The point here is that due to the 2 neighbors they do not interfere each other. The optimum is one draw per turn. That makes it kind of simple. My suggestion:

Iterate over the whole string
Count each group of white or black (a map would be helpful here)
Add each goup count to each over all count (i.e. add (block count - 2) when > 0)
Wendy wins when her over all count > Bob over all count