FastPrepFastPrep
Problem Brief

Count Special Substrings in a DNA Sequence

NEW GRADOA

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.

    1Example 1

    Input
    genome = "aabbaa"
    Output
    4
    Explanation
    Special substrings: "aa", "bb", "abba", "abba" Total: 4

    2Example 2

    Input
    genome = "pq"
    Output
    0
    Explanation
    No special substrings are present.

    3Example 3

    Input
    genome = "xyyx"
    Output
    2
    Explanation
    Special substrings: "yy" (Type 1), "xyyx" (Type 2)

    Constraints

    Limits and guarantees your solution can rely on.

    • 1 ≤ |genome| ≤ 300,000 

    public int countSpecialSubstrings(String s) {
  // write your code here
}
    Input

    genome

    "aabbaa"

    Output

    4

    Sign in to submit your solution.