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.