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

[KuldipGhotane]

Hello Guys. In this video I have made a small mistake (around 17th min) however I have highlighted it also cleared in the part 2 video.
So if you are having issue with left right array check part 2 it will get cleared.
Further if you need help do let me know I am just a comment away.
Thanks for stopping by.

[raghavsethi]

Best explanation for this question available on the internet.

[geekycoder]

This is best explanation I have got for this problem. Keep the good work bro

[ofuochi]

I always find myself on your channel after getting stuck on problems for days. Please which resource would you recommend to get better at thinking like this?

[kavyaagrawal]

why str[i]==str[i-1] so for this we can simply add frequency -1 for each iteration ..In this we have done -1?

[sealovingsoura]

Make a video in maximum palindrome hackerrank

[sealovingsoura]

Pleased help in this solution
My solution is I have created prefix and suffix frequency array of string
Then ans is sum of left array + if left i-1 ==right i+1 index && the condition you mentioned like ABA where A & A matches but B &A does not match I have given that condition .
In n where n is not large I am getting right and
But n is large my test case is failed
Its o(n) TC && I have declared long ans=0

[abiramiduraipandian]

following this video, left(i-1), right(i+1) makes no sense, as it contains the frequency from same side.and what is the need to have two arrays.can't it be done in one array, like left(i-1), left(i+1)?