All problems

Rearrangeable Palindrome Slices

Medium · prefix sum

A banner is made of coloured flags in a row. You are given a string s where each character is a letter from 'a' to 'j' and stands for one flag.

A slice is a run of one or more neighbouring flags. A slice is mirror-ready if its flags can be put in a different order, or left as they are, so that the row reads the same forwards and backwards.

Return how many slices of s are mirror-ready. Slices are counted by their position, so two slices with the same letters in different places count separately.

Examples

Example 1

Input: s = "aab"

Output: 5

The slices a, a, b, aa and aab work (aab can become aba). Only ab does not.

Example 2

Input: s = "abc"

Output: 3

Only the three single flags work. Any longer slice has at least two letters that appear once.

Example 3

Input: s = "abba"

Output: 8

Four single flags, plus bb, abb, bba and abba. The slices ab and ba do not work.

Constraints