Sol

考虑 dp。
首先容易发现，若一个串为回文串，那么不存在或仅存在一个数量为奇数的字符，其余字符数量皆为偶数。
我们考虑把 \(a\) 到 \(z\) 这些字符转化为 \(2^0\) 到 \(2^{25}\)，若一个子串为回文串，当且仅当这个串的异或值为 \(0\) 或 \(2\) 的幂。
记 \(f_i\) 表示前 \(i\) 个数可以分成的最小段数，\(sum_i\) 表示异或值的前缀和。
\(f_i=\min \left\{ f_j \right\} +1 \ (sum_i \ xor \ sum_j=0 \ or \ 2^x)\)
最后 \(f_n\) 即为答案。
时间复杂度 \(O(26n)\)

Code

//LYC_music yyds!
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0)
#define lowbit(x) (x&(-x))
//#define int long long
using namespace std;
int read()
{
	int pos=1,num=0;
	char ch=getchar();
	while (!isdigit(ch))
	{
		if (ch=='-') pos=-1;
		ch=getchar();
	}
	while (isdigit(ch))
	{
		num=num*10+(int)(ch-'0');
		ch=getchar();
	}
	return pos*num;
}
void write(int x)
{
	if (x<0)
	{
		putchar('-');
		write(-x);
		return;
	}
	if (x>=10) write(x/10);
	putchar(x%10+'0');
}
void writesp(int x)
{
	write(x);
	putchar(' ');
}
void writeln(int x)
{
	write(x);
	putchar('\n');
}
const int N=2e5+1;
string st;
int n,sum[1<<26],dp[N],now;
signed main()
{
	IOS;
	cin>>st; n=st.length(); st=' '+st;
	memset(sum,0x3f,sizeof(sum));
	sum[0]=0;
	for (int i=1;i<=n;i++)
	{
		int x=1<<(st[i]-'a');
		now^=x;
		dp[i]=sum[now];
		for (int j=0;j<26;j++) 
			dp[i]=min(sum[now^(1<<j)],dp[i]);
		dp[i]++;
		sum[now]=min(sum[now],dp[i]);
	}
	writeln(dp[n]);
}