algorithm - Game of flipping two consecutive positives to negatives -

i asked questions in 1 of interviews. questions goes this

you have string of '+' , '-' ( eg. ++----++++++-+--+ ). there 2 players player 1 , player 2. @ each turn 1 of player can choose 2 consecutive '+' i.e. ++ , flip them --. if initial string ++----++++++-+--+ , player has following 6 choices (2 - 7) .(first 1 reference).

1. ++----++++++-+--+
2. ------++++++-+--+
3. ++------++++-+--+
4. ++----+--+++-+--+
5. ++----++--++-+--+
6. ++----+++--+-+--+
7. ++----++++---+--+

the player takes turn 1 one. player plays last move win ( or lose - doesn't make difference).

given initial string , if player 1 takes first turn, have tell wins?

now seems classical game theory problem each player tries play optimally , @ each step plays move moves him winning position.

any ideas on how can approach solve ?

ps - interested more in approach in solving. have read http://www.codechef.com/wiki/tutorial-game-theory couldn't apply same logic here.

we can use grundy function here, because after converting ++ -- game divided sum of 2 separate games: left -- , right. let's assume g(l, r) value of grundy function [l, r] interval of given string. compute it, can try change ++ -- in possible positions, store g(l, k - 1) xor g(k + 2, r)(where k position ++ starts) values , choose smallest non-negative integer not among them. value base case(when there no possible moves) either 0 or 1(depending on whether last player loses or wins). first player wins if , if g(0, n - 1)(n lenght of input string) non-zero. solution has o(n^3) time complexity(there o(n^2) possible (l, r) pairs , can compute thr answer in linear time each of them).