from functools import lru_cache

def min_deletions(s: str) -> int:
    n = len(s)

    @lru_cache(None)
    def dp(i, j):
        if i > j:
            return 0
        if i == j:
            return 1

        res = dp(i + 1, j) + 1
        for k in range(i + 1, j + 1):
            if s[i] == s[k]:
                res = min(res, dp(i + 1, k - 1) + dp(k, j))
        return res

    return dp(0, n - 1)


# --------- Main stdin/stdout section ---------
if __name__ == "__main__":
    try:
        s = input().strip()
        if s:
            print(min_deletions(s))
        else:
            print(0)
    except Exception as e:
        print(0)