题目描述

给你一个字符串 $s$，请你将 $s$ 分割成一些子串，使每个子串都是回文串。

返回符合要求的最少分割次数。

输入格式

一行一个字符串 $s$，仅由小写英文字母组成，长度满足 $1 \le |s| \le 2000$。

输出格式

输出一行一个整数，表示将字符串 $s$ 分割成若干回文子串所需的最少分割次数。

样例输入 1

aab

样例输出 1

1

样例解释 1

只需一次分割就可将 $s$ 分割成 ["aa","b"] 这样两个回文子串。

样例输入 2

baaaabaa

样例输出 2

1

说明/提示

• $1 \le |s| \le 2000$
• $s$ 仅由小写英文字母组成