Скачать или смотреть Special String Again hackerrank solution part 1 (explanation)

In this problem we have two test cases
1. string with repeating char like aaaa
2. with different middle element like aba

for first we know all substrings will qualify for special string as single character is valid and remaining substring will also have same characters so in this case we can calculate no of substrings using n(n+1)/2 where n is length of string

However to check if all elements are equal you will either need one more for loop and frequency counter array hence we wont do that will try to solve the problem is single loop.

Approach :

first we will take two arrays left and right will will count frequency of each character and how many times it repeated previously (left arr for left to right and vice versa for right)

lets take string aababba
Here left arr will be [1211121]
and right arr will be [1121112]

This can be achieved with simple for loop for both arr just check ele with prev ele and increase the frequency

Now this precomputed frequency will help us to solve the problem in one loop as at any point we will know for every character how many char are repeated on both

Main solution
Take a for loop 0 to n and
Add a counter ;
We need to focus on two condn which are mentioned above

1. check if str[i-1]==str[i+1] && str[i] != str[i-1]
This will give substring with different char at middle and repeated on sides and now we will count how many similar chars on side. (using min of left[i-1] && right[i+1])

2. str[i]==str[i-1] so for this we can simply add frequency -1 for each iteration

Also keep in mind to treat end condition wisely(separately)

0:00 Start
1:10 Problem Definition
3:25 Naive Solution
7:26 Logic Building for repeated characters
10:39 Logic Building for Second Case
14:00 Optimized approach