PROBLEM LINK:
Author: Jingbo Shang
Tester: Xiaoxu Guo
Editorialist: Pushkar Mishra
DIFFICULTY:
Medium-Hard
PREREQUISITES:
Strings, Tries, Rolling Hash, Palindromes
PROBLEM:
Given N words, S[1..N], output the number of ordered pairs (i,\,j) such that S[i] concatenated with S[j] gives a palindrome.
EXPLANATION:
Let there be two words x and y. Let us look at the cases that arise when they are concatenated (i.e., x+y) from the point of view of palindromes:
-
Case 1: length(x) < length(y):
In this case, let us assume that y' is that suffix of y which is of the same length as x. If x+y is to be a palindrome then two conditions must be true - x = y' and y-y' is a palindrome. For example, aba and ccaba will form a palindrome upon concatenation but aba and cdaba wonât. -
Case 2: length(x) > length(y):
In this case, let us assume that x' is that prefix of x which is of the same length as y. If x+y is to be a palindrome then two conditions must be true - y = x' and x-x' is a palindrome. -
Case 3: length(x) = length(y):
In this case, if x+y is to be a palindrome then x = y.
These three cases lead us to formulate an algorithm. We need a data structure which can match prefixes of strings quickly. A trie is exactly for this purpose. We will take the words one by one, and put them in the trie. Before inserting word i, we will first find the number of words already in the trie that it forms a palindrome with upon being concatenated (word i being the second part in concatenation), and then insert it.
For finding the required numbers, we need to store two variables per node of the trie: uptill and below. The variable uptill stores the number of words that have the exact same letters as the ones from the root of the trie to this node. The variable below stores the number of those words w that have a prefix w\' which contains the exact same letters as the ones from the root of the trie to this node and w-w\' is a palindrome.
Keeping these operations in mind, we can define our insert(w) and getanswer(w) functions. The insert(w) function inserts the word w into the trie and getanswer(w) calculates the number of words already in the trie with which w would form a palindrome upon being concatenated.
We first define how getanswer(w) works. It first reverses w. Letâs call the new string revw. Then it starts at the root of the trie and goes down as per the letters of revw. When it is at a node which is at depth i from the root, it has already processed the first i letters of revw, i.e., the prefix of length i. Let us call the processed prefix revw'. If revw-revw' is a palindrome, then the word w can form palindrome upon being contenated with the words ending at this particular node. Hence, if revw-revw' is a palindrome, we add the value stored in uptill variable of this node to the answer (this counts all possibilities under case 1). Once we reach the node which is the last letter of revw, we add the values stored in the below and uptill variables of this node to our answer. This counts possibilities under case 2 and case 3.
The insert(w) works in a similar way. For this, we donât have to reverse the word. We start at the root and go down the edges as per the letters in w. When we are at a node at depth i from the root, we have already processed the prefix w' of length i. At this node, we add 1 to the value stored in below variable if w-w' is a palidrome. When we reach the node which is last letter of w, we add 1 to the uptill variable of the node.
How can we efficiently check whether a prefix of a word is a palidrome or not? We can use ârolling hashâ to calculate for a given word w of length N an array mark in \mathcal{O}(N) where mark[i] = 1 if the prefix w[0..i] is a palidrome and 0 otherwise. Thus we can preprocess each string before inserting it or calculating the number of strings it forms palindromes with upon concatenation. Please see the authorâs/editorialistâs solution for an example of rolling hash. You can read more about it from these links:
COMPLEXITY:
\mathcal{O}(N)
