Symmetric Substring Count

Medium

Given a string s, determine the total count of symmetric substrings present within it. A symmetric string is one that reads identically from both ends—meaning the sequence of characters is the same whether you traverse from left to right or right to left. For example, "radar" and "level" are symmetric, while "hello" is not. A substring is any contiguous sequence of characters extracted from the original string. Each single character is inherently symmetric, and longer symmetric substrings may be formed by characters that mirror around a center point. Your task is to count every symmetric substring, including overlapping occurrences and individual characters. Two substrings are considered different if they start or end at different positions in the string, even if they contain the same characters.

Example 1

Input

s = "abc"

Output

Explanation

The string contains exactly three symmetric substrings, each being a single character: "a", "b", and "c". No multi-character symmetric substrings exist since "ab", "bc", and "abc" do not read the same forwards and backwards.

Example 2

Input

s = "aaa"

Output

Explanation

There are six symmetric substrings: three single-character substrings "a" at positions 0, 1, and 2; two double-character substrings "aa" starting at positions 0 and 1; and one triple-character substring "aaa" spanning the entire string. Each occurrence counts separately.

Example 3

Input

s = "aba"

Output

Explanation

The symmetric substrings are: "a" (position 0), "b" (position 1), "a" (position 2), and "aba" (the full string). Note that "ab" and "ba" are not symmetric as they do not read the same in both directions.

Constraints

1 ≤ s.length ≤ 1000
s consists of lowercase English letters only (a-z).