FastPrep
Problem · String

Count Dominant Substrings

● MediumAmazonFULLTIMEOA
See Amazon 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:

    1. String s: the string to analyze

    Returns

    int: the number of dominant substrings

    Examples
    01 · Example 1
    s = "aaaaid"
return = 3

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

    02 · 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).
    The dominant substrings are "ab", "ba", another occurrence of "ab", and "abab", making a total of 4.

    Constraints
    ^~^
    More Amazon problems
    drafts saved locally
    public int countDominantSubstrings(String s) {
  // write your code here
}
    s"aaaaid"
    expected3
    sign in to submit