## 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.