Alternate approach-
Given problem can be solved using bit set as well-
-
We give distinct bit id to each prefix alphabet( e.g let x=1 b=10 c=100 etc in case we have 3 alphabets in prefixes)
-
We maintain a map of suffixes where <suffix, val>, here val is an integer bitset and 1 bit represents prefixes that make funny word so if we have a funny words xbad, bbad; then ‘bad’ suffix will have val as 011 (continuing from example in point 1 taking 'x’and ‘b’ will result in funny word [hence bit 1 and 2 is set to 1] while taking ‘c’ will not so 3rd bit which belongs to ‘c’ is 0)
-
Then we iterate over set of distinct suffixes (let it be suffix) and take its XOR with all other suffixes (let it be suffix1)
, let it be called res (result) -
We take then take AND of res&suffix and call it m, and similarly res&suffix1 and call it n, then number of possible solutions between given pair of suffixes is bit_count(m)*bit_count(n) ( bit_count(n)bit_count(m) is taken next time when same pair is taken in reverse order)
eg-
let suffix ‘bad’ has val of suffix is 1010101
and ‘cat’ has value of suffix1 val 1111100 then
res is 0101001
and m=0000001 & n=0101000 so possible ways is bit count(m) bit count(n)
2 * 1 is our answer for given pair -
We add this value to count and print the result once all pairs is done
O(sufixf^2) is time complexity achievedPython solution- CodeChef: Practical coding for everyone