Problem · String
Count Dominant Substrings
Learn this problem● Medium
AmazonFULLTIMEOA
See Amazon hiring insightsAmazonFULLTIMEOAProblem statement
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':
Given a string s of length n, determine how many of its substrings are dominant strings.
Function
countDominantSubstrings(s: String) → int
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
Examples
Example 1
s = "aaaaid"return = 3'aa', 'id', and 'aaid' are dominant substrings.
Example 2
s = "abab"return = 4
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).
Constraints
^~^