Question Statement

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.

Approach:

• The trick to solve this problem is to find all substring for each of the two cases.

Case 1: All characters are same.

• For a string with n characters, we can make a total of n*(n+1)/2 substrings. Note substrings keep the same order and don't skip characters. For instance, aaaa will make a, aa, aa, aa, aaa, aaa and aaaa This is because, for a string of size n we can make n - 1 substrings of size 2 and n - 2 substrings of size 3 and so on. This can be generalized as n-(k-1) where k is the length of the substring. So total number of substrings (of all lenghts) is then n-1 + n-2 + ... + n - (k-1) + ... + n - (n-1). This when written in reverse is same as 1 + 2 + ... + n-2 + n-1 + n. The sum of an arithmetic sequence is = n*(first+last)/2. Therefore, the sum of above sequence is n*(1+n)/2

Case 2: Odd length string with all characters same except the middle one

• For a string like aaabaaa, the total number of special substrings is equal to the number of repeated characters. For the example above it will be, aba, aabaa, aaabaaa. So when we find a character, c, such that its previous character, pc, is same as its next character, nc, i.e. pc == nc but not same as itself, i.e. pc != c, we can count the number of times that pc and nc are repeated. Note that, number of times pc is repated may be different than the number of times nc is repated, for instance aaabaa. We take the minimum of the repeated times. To add effeciency, we can create an array that stores the number of times a character is repated at every index. For example, for a string like aaabaa the array will contain 333122

Dry Run:

Code:

long substrCount(int n, string s) {

vector<int> same_char_count(n,0);
long ans=0;
int i=0;

while(i<n)
{
    int count=1;
    int j=i+1;
	
    while(j<n && s[i]==s[j])
    j++,count++;
	
    ans += (count*(count+1))>>1;
    same_char_count[i]=count;
    i=j;
}

for(int i=1;i<n-1;i++)
{
    if(s[i]==s[i-1]) same_char_count[i]=same_char_count[i-1];
    
    //odd length substr(s) which has middle element diiferent
    if(s[i-1]==s[i+1] && s[i-1]!=s[i]) ans += min(same_char_count[i-1],same_char_count[i+1]);
}

return ans;
}