121: Palindrome partitioning

Дана строка, верните минимальное число разбиений необходимых для разбиения данной строки на палиндромы

 

Пример 1

Input:   aba 

Output:  0

Пояснение: aba это палиндром

Пример 2

Input:   aacc 

Output:  1

Пояснение: aa и cc