Hackerrank - Special String Again Solution

A string is said to be a special string if either of two conditions is met:

• All of the characters are the same, e.g. aaa.
• All characters except the middle one are the same, e.g. aadaa.

A special substring is any substring of a string which meets one of those criteria. Given a string, determine how many special substrings can be formed from it.

For example, given the string , we have the following special substrings: .

Function Description

Complete the substrCount function in the editor below. It should return an integer representing the number of special substrings that can be formed from the given string.

substrCount has the following parameter(s):

• n: an integer, the length of string s
• s: a string

Input Format

The first line contains an integer, , the length of .
The second line contains the string .

Constraints

Each character of the string is a lowercase alphabet, .

Output Format

Print a single line containing the count of total special substrings.

Sample Input 0

5
asasd

Sample Output 0

7

Explanation 0

The special palindromic substrings of  are

Sample Input 1

7
abcbaba

Sample Output 1

10 

Explanation 1

The special palindromic substrings of  are

Sample Input 2

4
aaaa

Sample Output 2

10

Explanation 2

The special palindromic substrings of  are

Solution in Python

from itertools import groupby

def k_sum(k):
    return (k*(k+1))//2

def substrCount(n, s):
    case_a = 0
    case_b = 0
    for x,y in groupby(s):
        case_a += k_sum(sum(1 for i in y))
    for i in range(1,len(s)-1):
        skip = 1
        if s[i-skip] == s[i] or s[i+skip] == s[i]:
            continue
        match = s[i-skip]
        while i-skip>-1 and i+skip<len(s) and s[i-skip]==match and s[i+skip]==match:
            case_b += 1
            skip += 1
    return case_a + case_b

n = int(input())
s = input()
print(substrCount(n, s))

To solve it efficiently we have to consider  Cases:

Case 1: All special substrings have same character:

We can handle this case by simply counting the same continuous character and using formula K*(K+1)/2 (total number of substring possible : Here K is count of Continuous same char).

def k_sum(k):
    return (k*(k+1))//2

Example: In string "baaaa"

There are 2 substrings of continuous characters: b, aaaa

Length of string "b" = K = 1

Total number of substring = 1*(1+1)/2 = 2/2 = 1, is correct

Length of string "aaaa" = K = 4

Total number of substring = 4*(4+1)/2 = 20/2 = 10, is also correct

Note: K*(K+1)/2 is a shortcut for calculating sum(range(K+1)) i.e. 1+2+3+....+K

We use itertools groupby function to group all same continuous character substring then calculate k*(k+1)/2 for each substring which gives us count of total possibilities of case 1.

case_a = 0
case_b = 0
for x,y in groupby(s):
    case_a += k_sum(sum(1 for i in y))

Case 2: All special substrings have same character except one in the middle:

We loop through our string s from index 1 to index n-1 and assume each character as center of a substring then we check upto how many characters the characters in left and right part are same.

We also have to check if the characters in left and right part doesn't match our mid character.

Example, "aabaa" is valid and will be counted whereas "aaaaa" though valid will not be counted because it's already counted in case 1.

for i in range(1,len(s)-1):
    skip = 1
    if s[i-skip] == s[i] or s[i+skip] == s[i]:
        continue
    match = s[i-skip]
    while i-skip>-1 and i+skip<len(s) and s[i-skip]==match and s[i+skip]==match:
        case_b += 1
        skip += 1

So, we count total substrings from both cases.