You can learn more about what to expect in these emails here.
Table of Contents
Problem
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}
You can learn more about what to expect in these emails here.
Our website uses cookies to make your browsing experience better. By using our site you agree to our use of cookies. Learn more by reading our privacy policy.