FastPrep
Problem · String

Count Special Substrings in a DNA Sequence

● MediumAmazonNEW GRADOA
See Amazon hiring insights

You are given a DNA sequence string genome, consisting of lowercase Latin letters.

A substring of genome is considered special if it satisfies one of the following conditions:

  • The length of the substring is exactly 2 and both characters are the same. Example: "aa", "bb"
  • The length of the substring is greater than 2, the first and last characters are the same, and the substring in between (from index 1 to n-2) contains exactly one distinct character. Example: "xyyx" -> 'x' == 'x' and the middle "yy" has only one distinct character.

    • Function Signature

    def countSpecialSubstrings(genome: str) -> int:

    Input

    • A single string genome of length n where:

    • 1 ≤ n ≤ 3 * 10^5
    • genome contains only lowercase letters ('a' to 'z')

    Output

    • Return the total count of special substrings in the given genome string.

    Examples
    01 · Example 1
    genome = "aabbaa"
return = 4
    Special substrings: "aa", "bb", "abba", "abba" Total: 4
    02 · Example 2
    genome = "pq"
return = 0
    No special substrings are present.
    03 · Example 3
    genome = "xyyx"
return = 2
    Special substrings: "yy" (Type 1), "xyyx" (Type 2)
    Constraints

    • 1 ≤ |genome| ≤ 300,000

    More Amazon problems
    drafts saved locally
    public int countSpecialSubstrings(String s) {
  // write your code here
}
    genome"aabbaa"
    expected4
    sign in to submit