Как разбить строку на как можно меньше палиндромов?

Это вопрос интервью : «Вам дана строка, и вы хотите разбить ее на как можно меньше строк, чтобы каждая строка - это палиндром ». (Я предполагаю, что строка из одного символа считается палиндромом, т.е.« abc »разбивается на« a »,« b »,« c ».)

Как бы вы ответили на него?