HACKERRANK : SPECIAL STRING AGAIN [ INTERVIEW 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.

[@aldrincantero2101]

nice to know the solution of this problem hehehe, but I want to know where did you get the formula n x (n + 1)/2?

[@ilyichelgar4493]

i'm confused with that formula too

[@AnandPandeyHere]

Its the formulae for calculating total number of substring from a string of length n.
You can read more about it from here
stackoverflow.com/questions/12418590/finding-substrings-of-a-string#:~:text=For%20any%20substring%20we%20have,2%20pairs%20of%20distinct%20characters.

[@ankitranjan8363]

@@AnandPandeyHere then why didn't you directly used n=4 for "aaaa". why the need to calculate "repeat"

[@ankitranjan8363]

also... how did you come to conclusion that since all single letters are already counted , so use n-1 instead of n in the formula

[@AnandPandeyHere]

@@ankitranjan8363 Because here we have to consider single elements too, now if I will use N directly, It will be difficult for me at the end to check which single elements did I miss. So, counting the single elements first and using the formulae for N-1 same elements would be a more readable and better solution. No wonder, you can do it the other way too, but this is much more simple for understanding purpose.

[@karthikeyans2825]

Amazing solution! Thanks for this!

[@monicagerard900]

Very clear explanation and nice, concise solution. Bravo!

[@AnandPandeyHere]

Thanks Monica!

[@adityajha9110]

Same logic in python doesn't work for me.
ans = len(s)
for i in range(len(s)):
#repetitive substring case
repeat = 0
while i+1 < len(s) and s[i] == s[i+1]:
i += 1
repeat += 1
ans += (repeat*(repeat+1))//2
#palindromic substring case
pointer = 1
while i-pointer >= 0 and i+pointer < len(s) and s[i+pointer] == s[i-1] and s[i-pointer] == s[i-1]:
ans += 1
pointer += 1
return ans

[@davidhackro1425]

This part is very interesting ~ repeat (repeat + 1) / 2 ~, in essence it is the gauss formula ~ ∑=(n)(n+1)2 ~

[@AnandPandeyHere]

You got it right

[@parnitasharma8898]

looked everywhere for such a solution...thank you so much

[@AnandPandeyHere]

Happy to help

[@saicharan4669]

Bro in the for loop that first case will be repeating right , doesn't that affect the answer ??

[@yashsalvi5043]

For second while loop, can anyone tell me where have we initialized the 'i' int ?!

[@amitshah1630]

For this block of code:
while( i + 1 < s.length() && s.charAt(i) == s.charAt(i+1)){
repeat++;
i++;
}
it will always give one less repeat count.
eg:
for "aaaa"
repeat = 0, i = 0;
1st 'a' == 2nd 'a' --> repeat = 1 , i = 1
2nd 'a' == 3rd 'a' --> repeat = 2 , i = 2
3rd 'a' == 4th 'a' --> repeat = 3 , i = 3
loop ends ( i + 1 < s.length() => 3+1 < 4 => false)
Total repeat count = 3 instead of 4
How did your code pass for test case aaaa?

[@AnandPandeyHere]

String s = " aaaa"
Count=3
so, ans=s.length()+ ((count*(count+1))/2) ;
ans=4+((3*4 )/ 2);
ans=4+6=10
The Special Strings :
Length 1: "a " , "a" , "a" , "a"
Length 2 : "aa" , "aa" , "aa"
Length 3: "aaa" , "aaa"
Length 4: "aaaa"
Hence the answer will be 10 for this case.
Hope it helps.

[@amitshah1630]

@@AnandPandeyHere my mistake. I thought it was n*(n-1)/2

[@anmolcoolsinha]

for the second case, why are you using charAt(i+pointer)==charAt(i-1) and not charAt(i+pointer)==charAt(i-pointer) ?

[@AnandPandeyHere]

Because the string should have only one alphabet different, if I'll do charAt(i+pointer) ==charAt(i-pointer).. Then for the this string "abcba" for i=3, whole string "abcba" will also get counted. And we know according to the question, abcba is not a special string. Hope you get the difference.

[@anmolcoolsinha]

@@AnandPandeyHere Oh yes, I missed on that. Thanks !

[@desiwriter4645]

in 2nd case use 1st and n-1th pointer

[@rishishrestham8681]

thanks dude , that was really helpful

[@AnandPandeyHere]

Glad to hear it!

[@shashanksharma9829]

Bro in the second case if we will put aaaa then why it is not get incremented

[@AnandPandeyHere]

I am checking for the strings with all common letters first and incrementing our pointer such that it comes under our first case... The second case is where one letter is dissimilar .

[@ardey7]

I implemented the same logic as well as the same code but could not pass testcases.(eg aaaa)
Please help , let me know if I am doing something wrong.
Thanks in advance.
def okay(i,dist,string):
if(i+dist=0):
return True
else:
return False
def string_check(string):
ans=len(string)
for i in range(len(string)):
counter=0
while(i+1

[@amitshah1630]

I am thinking same, how his test cases passed.
while(i+1

[@skumakerguitar8708]

@@amitshah1630 there is no problem with the code i think he loop with aa,aa,aa and calculate with formula n * n+1 / 2 = 6 + str.length() the result is satisfy right?