Given $$$N$$$ strings, we need to count how many pairs $$$1$$$ <= $$$i$$$, $$$j$$$ <= $$$N$$$ exists such that s[i] + s[j] is a Palindrome. Can anyone suggest an efficient approach for solving this problem?
1 <= $$$N$$$ <= 2000
1 <= |si| <= 1000
The lengths of all strings are not necessarily same.
My approach is to precompute hashes of the given strings and iterate over all pairs i, j now we want to concatenate the two strings s[i] + s[j]. For simplicity let's say length(s[i]) <= length(s[j])
1) if length(s[i]) == length(s[j]) then hash(s[i]) should be equal to hash(s[j]).
2) take suffix of s[j] of length equal to s[i] and check if they are equal and also remaining prefix of s[j] excluding the previous suffix should be palindrome.
