Problem Brief

Count Dominant Substrings

FULLTIMEOA

See Amazon online assessment and hiring insights

A team of data analysts at Amazon is working to identify patterns in data. During their analysis, they discovered a category of strings they call a 'dominant string':

The string has an even length.

The string contains at least one character with a frequency equal to exactly half the length of the string.

Given a string s of length n, determine how many of its substrings are dominant strings.

Function Description

Complete the function countDominantSubstrings in the editor.

countDominantSubstrings has the following parameter:

String s: the string to analyze

Returns

int: the number of dominant substrings

1Example 1

Input

s = "aaaaid"

Output

Explanation

'aa', 'id', and 'aaid' are dominant substrings.

2Example 2

Input

s = "abab"

Output

Explanation

Here are the dominant substrings in s = "abab":

"ab" (from position 0 to 1):
- Length 2, 'a' and 'b' both appear once, which is exactly half of the length (2 / 2 = 1).
"ba" (from position 1 to 2):
- Length 2, 'b' and 'a' both appear once, which is exactly half of the length (2 / 2 = 1).
"ab" (from position 2 to 3):
- Length 2, 'a' and 'b' both appear once, which is exactly half of the length (2 / 2 = 1).
"abab" (from position 0 to 3):
- Length 4, 'a' appears twice, which is exactly half of the length (4 / 2 = 2).

The dominant substrings are "ab", "ba", another occurrence of "ab", and "abab", making a total of 4.

Constraints

Limits and guarantees your solution can rely on.

^~^