Symmetric Substring Count

MEDIUM25 pts

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

Input

s = "abc"

Output

3

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

Input

s = "aaa"

Output

6

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

Input

s = "aba"

Output

4

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.

Accepted0/0·0% Acceptance

Constraints

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

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

s =

"abc"

Symmetric Substring Count

Hints

Symmetric Substring Count

Hints