Воспользуемся методом динамического программирования, где dp[i][j] - ответ для подстроки S с i по j. Если i и j совпадают, ответ будет 2 + dp[i + 1][j - 1], иначе нужно удалить первый или последний символ и искать ответ для него: dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]).
Ответ на задачу будет в dp[1][n].
Реализацию удобно сделать двумя циклами - по i с n до 1, по j с i + 1 до n.