PALINDROMIC SUBSTRING

★★★★★

1 votes

Details

Problem

Given string S containing atmost two character 'a' and 'b' of length N , you have to rearrange it in such a way that number of palindromic substring are maximum.There are multiple ways to arrange the string.

You have to print the count of palindromic substring in this new string.

Input Format

Single line containing a string.

Output Format

Singe line containig an interger

Constraint

Size of string is 1<=N<=1000000

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

For "aabb", there are 6 palindronic substring {a,a,aa,b,b,bb}

The string "abab" also have 6 palindromic substring {a,b,a,b,aba,bab}