This line is not very efficient: temp = temp+S[cnt];
1 Like
Thanks buddy. Understood my mistake.
+= operator is much more efficient than + operator in case of concatenation (now no new copy of string is created).
From the same reason as anupam_datta in his question here. Do not pass string by value to a palindrome checking function.
My (simplified) understanding of the solution:
Iterate over all possible values of the Order p (starting from 2) and treat every index i as centre of the palindromic subsequence. Treating i as the centre allows us to check if the subsequence is a palindrome on the fly, because we only have to check the newly added peripheral characters on the left and the right. We are assured that the subsequence we have till now is a palindrome already, so we only have to check if the newly added characters on the left and right of the subsequence match each other or not. Be careful to consider 2 cases here:
First Case (Your palindrome is an odd length palindrome):
The character at index i can be the centre of a palindrome so in this case you have to check the characters to the left and right(not immediate left and right) of i. Call them start and finish. Initially, start will be equal to i/p and finish will be equal to i X p… if start and finish are equal, then great, increment your answer by 1 and set start = start/p and finish = finish X p. Obviously if start and finish violate any boundary conditions like start%p !=0 OR finish > length of string OR obviously if character at start != character at finish, then you should break from this inner loop and start considering the next index i+1 as the centre of your palindromic subsequence.
Second Case (Palindrome is of even length:) Treat the index i as one of the 2 characters which form the centre of your even length palindrome. In this case the start will be equal to i (instead of i/p) and finish will be the same as previous case: i*p. Perform the same checks as before, checking everytime if start==finish and if yes, set start = start/p and finish = finish/p. Break if start%p != 0 OR if finish is greater than the length of the string OR if start != finish.
Caveat: As mentioned in the editorial, you will have to add the length of the string to your answer because every subsequence of length is a valid answer. This hack allows us to start considering subsequences whose length is at least 2, otherwise, as mentioned, we will end up with an O(n^2) algorithm, which will fail horribly.
Please see the linked tester’s excellent solution for the implementation details.