Use dynamic programming.

Let dp[i][j] be the solution for the sub-array from index i to index j.

Notice that if we have S[i] == S[j] one transition could be just dp(i + 1, j + 1) because in the last turn we would have a palindrome and we can extend this palindrome from both sides, the other transitions are not too difficult to deduce.