Untitled

import java.util.Scanner;

/**
 * 动态规划解法 - 时间复杂度 O(n^2)
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        
        if (s == null || s.isEmpty()) {
            System.out.println("0");
            return;
        }
        
        int n = s.length();
        
        // dp[i] 表示前i个字符的最少分段数
        int[] dp = new int[n + 1];
        
        // 初始化：最坏情况每个字符一段
        for (int i = 1; i <= n; i++) {
            dp[i] = i;
        }
        
        // 对于每个结束位置i
        for (int i = 1; i <= n; i++) {
            // 尝试所有可能的起始位置j
            for (int j = 0; j < i; j++) {
                // 检查s[j...i-1]是否能形成回文段
                if (canFormPalindrome(s, j, i - 1)) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        
        System.out.println(dp[n]);
        scanner.close();
    }
    
    /**
     * 检查s[start...end]是否能重排为回文串
     * 即最多只有一个字符出现奇数次
     */
    private static boolean canFormPalindrome(String s, int start, int end) {
        int[] count = new int[26];
        
        for (int i = start; i <= end; i++) {
            count[s.charAt(i) - 'a']++;
        }
        
        int oddCount = 0;
        for (int c : count) {
            if (c % 2 == 1) {
                oddCount++;
            }
        }
        
        return oddCount <= 1;
    }
}