{ Special String Again }

Solving the Programming Challenge

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 the Free Newsletter

A free, weekly e-mail with the best new articles, courses, and special bonuses.

We won't send you spam. Unsubscribe at any time.