Thank you for your interest in Software Development Engineering opportunities at Amazon

Amazon近期发放的OA越来越难了，今天更新的又是一道超难的题目，我们一起看看吧。

Code Question 2

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

• It has an even length.
• And the string contains at least one character having frequency matching the exactly half of the length of the string.

Given a string s of length n, determine the number of its distinct substrings that are dominant strings.

Example

s = "idafddfi"

All even-length substrings of s with a frequency of any character that is exactly half their length are:

Substring	Length of Substring	Frequent Character	Frequency of Character
id	2	d/i	1
da	2	d/a	1
af	2	a/f	1
fd	2	f/d	1
df	2	d/f	1
fi	2	f/i	1
dafd	4	d	2
afdd	4	d	2
fddf	4	f/d	2
dfii	4	i	2
idafdd	6	d	3
dafddf	6	d	3

There are 13 dominant substrings in s.

---

Function Description

Complete the function getDominantStringCount in the editor below.

getDominantStringCount has the following parameter:

• string s: the string to analyze

Returns

• int: the number of dominant substrings in s

Constraints

• 1 ≤ n ≤ 10^5
• s consists of lowercase English letters in the range 'a' to 'j' (inclusive) only.

---

Sample Case 0

Input:

s = "aaaaiid"

Output:

3

Explanation:

The dominant substrings are:

• ai
• id
• aaid

我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。

We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.