Try to use dynamic programming to solve the problem.

let dp[i] be the answer for the prefix s[0…i].

The final answer to the problem will be dp[n-1]. How do you compute this dp?