Count-of-palindromic-substrings-in-an-index-range

#1

https://practice.geeksforgeeks.org/problems/count-of-palindromic-substrings-in-an-index-range/0/

thsi code shows wa on submission on geeks for geeks
plz make changes in my code and explain them…

dont provide link of editorial…

#2

ok, I’ll try and explain this to you.
for any character to be included in a palindromic substring, it has to be the following:

  1. 1 character, with itself, is palindrome
  2. it can be a palindrome with it’s adjacent characters, i.e. matching
  3. it’s adjacent characters are palindrome themselves like wow, mom, aba, aca etc
    so first you mark the diagonal, which u have done as well
    since all the characters of length 1 are palindromes with themselves
    now secondly, you have to check, that this character should be a terminating point or a beginning point, i.e. if aa is there then a at first position or at second position but since they are identical i will do it only once, so in ur code you have taken the second position and marked the indices on the right of the diagonal
    now comes the tricky part
    so let us cosider
    11011 sort of thing
    if u have marked 101 as a palindromic string and now ur marking 11011 u need to take all the strings in 11011 and increment ur count
    so u take
    dp[i][j] will be addition of number

of palindromes from i to j-1 and i+1

to j subtracting palindromes from i+1

to j-1 (as counted twice) plus 1 if

str(i..j) is also a palindrome

#3

i have coded the problem using the approach where we check for strings of all sizes using tabulated manner only but i am getting wrong ans i cant figure out why so plz make changes in my code so that i get correct ans on gfg on submission…
make changes in my code…

i have tried to count palindromic substring in substring of this string geneerated using the index given in ques…this is what i have done…

actually there is also a problem to count palindromic substrings in a given string so i just implemented that here …so correction of code will also help me to corrct that code as well…plz reply at the earliest…

#4

in your code:
for(int i=3;i<=n;i++)

{

for(int j=0;j<n-i+1;j++)

{

   int k=i+j-1;

   if(dp[j+1][k-1]==1&&a[j]==a[k])

   {

       dp[j][k]=1;

       count++;

   }

}

}
this part is a bit unclear, cna you walk me through?
I mean it does not align with approach or the question

#5

i have tried to count substring of length 3 or more length whether they are palindrmic or not
i have looked at first and last char and if same then i have looked at inner characters(1 forward and 1 backward from start and end ) dp table if it is 1 then it is a palindrome

#6

Have you tried drawing the DP table on paper once?
Draw it once, and you will notice one thing. MISSING INDICES. which is equivalent to missing combinations
and in cases of odd and even
in odd, this still might work, since xyx is a palindrome
but for even when u check for xyyx at either y it will give false even for x when u check inside it will return false, since by remove x from yyx the resultant is not palindrome
at each step u need to recheck

#7

in xyyx i will remove both x from front and end (sice they are same char and match) and then check for inner string which is left yy whether it is a palindrome or not…

also when i run the code for xyyx it gives ans as 6
x
y
x
x
xyyx
and yy
which is correct

#8

why arent u replying???plz reply its been days

#9

Why aren’t you replying properly plz clear the doubt properly ??
Or else I willl have to report this