#include<iostream>
#include<cstring>
using namespace std;
char input_str[510];
int dp[510][510];
int dp_solve(int left, int right) {
if (left >= right)
return 1;
if (dp[left][right])
return dp[left][right];
int ans = right - left + 1;
if (input_str[left] == input_str[right])
ans = min(ans, dp_solve(left + 1, right - 1));
for (int i = left; i < right; i++)
ans = min(ans, dp_solve(left, i) + dp_solve(i + 1, right));
dp[left][right] = ans;
return ans;
}
int main() {
cin>>input_str;
int str_length=strlen(input_str);
cout<<dp_solve(0, str_length-1)<<endl;
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGNzdHJpbmc+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY2hhciBpbnB1dF9zdHJbNTEwXTsKaW50IGRwWzUxMF1bNTEwXTsKCmludCBkcF9zb2x2ZShpbnQgbGVmdCwgaW50IHJpZ2h0KSB7CgogICAgaWYgKGxlZnQgPj0gcmlnaHQpCiAgICAgICAgcmV0dXJuIDE7CgogICAgaWYgKGRwW2xlZnRdW3JpZ2h0XSkKICAgICAgICByZXR1cm4gZHBbbGVmdF1bcmlnaHRdOwoKICAgIGludCBhbnMgPSByaWdodCAtIGxlZnQgKyAxOwogICAgaWYgKGlucHV0X3N0cltsZWZ0XSA9PSBpbnB1dF9zdHJbcmlnaHRdKQogICAgICAgIGFucyA9IG1pbihhbnMsIGRwX3NvbHZlKGxlZnQgKyAxLCByaWdodCAtIDEpKTsKCiAgICBmb3IgKGludCBpID0gbGVmdDsgaSA8IHJpZ2h0OyBpKyspCiAgICAgICAgYW5zID0gbWluKGFucywgZHBfc29sdmUobGVmdCwgaSkgKyBkcF9zb2x2ZShpICsgMSwgcmlnaHQpKTsKCiAgICBkcFtsZWZ0XVtyaWdodF0gPSBhbnM7CgogICAgcmV0dXJuIGFuczsKfQppbnQgbWFpbigpIHsKCiAgICBjaW4+PmlucHV0X3N0cjsKCiAgICBpbnQgc3RyX2xlbmd0aD1zdHJsZW4oaW5wdXRfc3RyKTsKCiAgICBjb3V0PDxkcF9zb2x2ZSgwLCBzdHJfbGVuZ3RoLTEpPDxlbmRsOwoKICAgIHJldHVybiAwOwp9Cg==