I didnt attempted it.

# April19 - Problem Discussion

**l_returns**#24

@vijju123 as well as @taran_1407 (the setter) helped me in that problem…

I gave their names as a seed in the random function

vijju123 gave max score…

**aniket_sanghi**#26

My solution to `KLPM ( KMP? )`

Let me present my solution through an example.

**Approach** - For each pair of indices 1≤ i < j ≤ n ,find the number of ways of finding string `s1`

and `s2`

such that `s1 + s2`

is a palindrome and `s1`

start at i and `s2`

end at j. Then we can just loop over all i and j and sum up to find our answer.

**But HOW ?**

Lets think inductively ( DP? )

Now consider this example

s = `abcdecba`

Consider i = 1 & j = 8

`a bcdecb a`

Now since, s_i == s_j implies it is possible to find such `s1`

and `s2`

**( Why? )**

Clearly one such possibility is `s1 = "a"`

and `s2 = "a"`

Next lets check for other ways :

- Case 1 :
`s1 = "ab.."`

and`s2 = "..ba"`

. Clearly the number of ways of doing so is equal to number of ways of finding`s1`

and`s2`

with i = 2 and j = 7 - Case 2:
`s1 = "ab.."`

and`s2 = "a"`

.

Aha! Now we arised with a problem, how many such strings are possible?

Should I loop and find out in O(n^3)?

Lets check what we actually need!

`Requirement 1`

- Number of Palindromic substrings starting at i + 1**( Isn’t it? )** - Case 3:
`s1 = "a"`

and`s2 = "..ba"`

.

Kinda similar to Case 2!

Same requirement?

Nope! But similar!

`Requirement 2`

- Number of Palindromic substrings ending at j - 1**( Similar? )**

Now, Our Target is to find these 2 requirements in O(n^2)

**Requirement 1**

For each pair 1 \le i \le j \le n Find the number of *substrings of* “s_i{s}_{i+1}......{s}_{j-1}s_j” which start with s_i and is a palindrome! **( Right? )**

Similarly for **Requirement 2**

How?

`Hint: Make isPal[i][j] where isPal[i][j] = 1 if`

“s_i{s}_{i+1}......{s}_{j-1}s_j” `is a Palindrome else isPal[i][j] = 0`

( DP? )

**Still got Doubt? Ask in comments! **

Link to My Solution KLPM ( KMP? )

**adshin21**#27

Hey @aniket_sanghi , what does FPal and BPal stores here?

That makes me not to understand how the ans dp is calculated

**bhagirathi08**#29

Hi aryanc403

If you have time can you please post an editorial of XORMIN show that a beginner like me can also understand, as the official editorial is very unclear to me and to the community as well.

Whats is the “dsu ninja technique” which you mentioned as a part of solution to XORMIN?