Special String Again
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:
{m, n, o, n, o, p, o, o, non, ono, opo, oo}
Read more on the challenge page…
Problem Analysis and Solution
My Solution
I’m providing the solution for Python and JS, please leave on the comments if you found a better way.
def substrCount(n, s):
result = 0
i = 0
while (i < n):
char_count = 1
while (i + 1 < n and s[i] == s[i+1]):
i += 1
char_count += 1
result += int(char_count * (char_count + 1) / 2)
i += 1
for i in range(1, n):
char_count = 1
while (
i + char_count < n and
i - char_count >= 0 and
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 - 1
return result
function substrCount(n, s) {
let result = 0;
let i = 0;
// 1st case, all letters are the same
while(i < n) {
let charCount = 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++) {
let charCount = 1
while (
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
}
return result
}
Join more than a thousand developers!
Subscribe now to our free, weekly e-mail with the best new articles, courses, and special bonuses.
We won't send you spam. Unsubscribe at any time.