FastPrep

Description

Solutions

Count Dominant Substrings

🔥 FULLTIME📚RELATED PROBLEMS

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

Example 1:

Input:  s = "aaaaid"
Output: 3 
Explanation:
      
      'aa', 'id', and 'aaid' are dominant substrings.

Example 2:

Input:  s = "abab"
Output: 4 
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:

^~^