Special Palindromic Sequence

The first and only line of input contains a single string S.

Print a single string, either "Yes" or "No".

The string S must be split into two non-empty substrings. For a string of length n, there are n-1 possible split points.

A naive approach of re-calculating character frequencies for both substrings at every split point will be too slow (O(N²)).

Sample Input 1:

abacaba

Sample Output 1:

Yes

Explanation for Sample 1:

We can split the string S into s1 = "aba" and s2 = "caba".

Check s1 = "aba":
Character frequencies: {'a': 2, 'b': 1}.
The number of characters with an odd frequency is 1 (just 'b').
Since 1 <= 2, s1 is valid.

Check s2 = "caba":
Character frequencies: {'c': 1, 'a': 2, 'b': 1}.
The number of characters with odd frequencies is 2 ('c' and 'b').
Since 2 <= 2, s2 is also valid.

Because a valid split exists where both substrings satisfy the property, the string is a special sequence.

Sample Input 2:

abcde

Sample Output 2:

No

Explanation for Sample 2:

Let's check a possible split, for instance, into s1 = "ab" and s2 = "cde".

Check s1 = "ab":
Frequencies: {'a': 1, 'b': 1}.
Number of odd-frequency characters is 2. Valid (2 <= 2).

Check s2 = "cde":
Frequencies: {'c': 1, 'd': 1, 'e': 1}.
Number of odd-frequency characters is 3. Invalid (3 > 2).

Since s2 is invalid for this split, we must try other splits. However, no matter how the string abcde is split, at least one of the substrings will have more than two characters with odd frequencies. Therefore, it is not a special sequence.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

2 <= N <= 10^5
`S` consists of lowercase English letters.

Time limit: 1 sec