Minimum Removals to Eliminate Palindromic Subsequences

You are given a string s containing only lowercase English letters. Your task is to determine the minimum number of characters that must be removed from the string such that no palindromic subsequence of length \(\ge 2\) exists in the remaining string.

A subsequence is a sequence that can be derived from the string by deleting some or no elements without changing the order of the remaining characters. A palindrome is a string that reads the same forwards and backwards.

In other words, after removals, every possible subsequence with length \(\ge 2\) must not be a palindrome.

Hint: If the input string is of length 1, it already satisfies the condition. Otherwise, if any character appears at least twice, one removal is sufficient, because the only way to have no palindromic subsequence is for all characters to be distinct.

inputFormat

The input consists of a single line containing the string s.

Constraints:

• \(1 \le |s| \le 10^5\)
• s contains only lowercase English letters.

outputFormat

Output a single integer — the minimum number of characters that need to be removed from s so that there is no palindromic subsequence of length \(\ge 2\) in the resulting string.

a

0