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 s= mnonopoo, we have the following special substrings:
I’m providing the solution for Python and JS, please leave on the comments if you found a better way.
defsubstrCount(n, s):
result =0
i =0while (i < n):
char_count =1while (i +1< n and s[i] == s[i+1]):
i +=1
char_count +=1
result += int(char_count * (char_count +1) /2)
i +=1for i in range(1, n):
char_count =1while (
i + char_count < n and
i - char_count >=0and
s[i] != s[i-1] and
s[i-char_count] == s[i+char_count] and
s[i-1] == s[i-char_count]
):
char_count +=1
result += char_count -1return result
functionsubstrCount(n, s) {
letresult=0;
leti=0;
// 1st case, all letters are the same
while(i<n) {
letcharCount=1;
while (i+1<s.length&&s[i] ==s[i+1]) {
i++;
charCount++;
}
result+= parseInt((charCount* (charCount+1)) /2);
i++;
}
// 2nd case, palindrome
for (i=1; i<n; i++) {
letcharCount=1while (
i+charCount<s.length&&i-charCount>=0&&s[i-1] !=s[i] &&s[i-1] ==s[i-charCount] &&s[i-1] ==s[i+charCount]
) {
charCount++;
}
result+=charCount-1
}
returnresult
}