TEAMNAME - Editorial

Alternate approach-
Given problem can be solved using bit set as well-

  1. 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)

  2. 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)

  3. 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)

  4. 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)
    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

  5. We add this value to count and print the result once all pairs is done
    O(sufixf^2) is time complexity achieved

    Python solution- Solution: 43297879 | CodeChef

great approach…