Sharing my 0ms solution with detailed explanation:
First, let's apply standard backtracking/dfs with memoization, but keeping the game state abstract:
class Solution {
unordered_map<GameState, bool, GameStateHash> cache;
bool canWin(const GameState& s) {
auto it = cache.find(s);
if (it != cache.end()) return it>second;
vector<GameState> next = s.generatePossibleNextMoves();
for (const GameState & n : next)
if (!canWin(n)) return cache[s] = true;
return cache[s] = false;
}
public:
bool canWin(const string& s) { return canWin(GameState(s)); }
};
The naive implementation of a GameState can be a string with +/ and generatePossibleNextMoves() from the easy version of the problem.
Now, let's see how we can define the GameState to have 0ms runtime. In a nutshell, we can compress/reduce state space, by merging similar game states with the same outcomes (e.g. beginnerwins or beginnerloses).
Example: following game states are actually the same:
++++++++++++
++++++++++++
++++++++++++
++++++++++++
Thus, we can encode these states as (3,4,5): an ordered list of integers, where each integer is a length of a chains of consequtive +es.
It's also easy to see that singe + can be ignored. ++ and +++ same, so we can encode both ++ and +++ as 3 (for consistency), and skip 1s.
This is already pretty great state space reduction, isn't it? But we can do much better:
Consider “symmetric” states, where each number repeats even number of times (example: 3,3,4,4,9,9,9,9). It is easy to show that every symmetric state is a beginnerloses state. It is easy to show that winning strategy exists for the 2nd player, since 2ndplayer can always mirror the move of the opponent at each step. Thus, those “symmetric” states, being “beginnerloses” are equivalent to the empty state (). Similarly, it is also easy to show that removing a symmetric substate from the gamestate doesn't change the outcome. E.g. (5,5,6,6,6,7,7,7,7,8,8,8,8,8) after removing a symmetric substate (5,5,6,6,8,8,8,8) becomes (6,8).
Thus, each game state can be represented as a set of unique integers: set < int >
Note, that we need to implement generatePossibleNextMoves(), so we need to actively add and remove numbers to the set.
Addition a number to the set and removal of the number to the game state in our reduced state space becomes one operation: toggle(), which adds the number if it was absent and removes if it was present.
struct GameState {
set<int> chains;
int hash = 0;
GameState() {}
GameState(const string& s) {
int l = 0;
for (int i=0; i<=(int)s.size(); i++)
if (s[i]=='+') l++; else toggle(l), l = 0;
}
void toggle(int len) {
if (len<=1) return;
if (len==2) len = 3;
auto it = chains.find(len);
if (it == chains.end()) chains.insert(len); else chains.erase(it);
hash ^= len * len * len;
}
};
Generating possible moves is trivial:
struct GameState { // continued
vector<GameState> generatePossibleNextMoves() const {
vector<GameState> result;
for (int len : chains) {
GameState s = *this;
s.toggle(len);
if (len <= 3) result.push_back(s);
else {
for (int j=0; j<len2 && j<len/2; j++) {
GameState t = s;
t.toggle(j);
t.toggle(len2j);
result.push_back(t);
}
}
}
return result;
}
};
We also need a hashcode and equality comparer for the GameState, so we can use it as a key in unordered_map. For efficiency, the hash code is stored directly as a field, and updated incrementally on each toggle() operation.
struct GameStateHash { size_t operator() (const GameState& s) const { return s.hash; } };
bool operator == (const GameState& a, const GameState& b)
{ return a.hash == b.hash && a.chains == b.chains; }
Further optimization is possible:

instead of set<int>, you can also use bitset<> class.

instead of generating new set of possible moves you can incrementally change the state