The time complexity is linear in the number of characters of the strings during the radix bucketing step, but it's pretty hard to formulate the average complexity of the palindrome check. If anyone has any ideas...? Worst case complexity is probably when each string matches all of the others during the bucketing procedure, but all differ exactly 1 in length (e.g. "a", "aa", "aaa", "aaaa", ...)
I use an array of lists (ugly, I know) because I expect the bucket occupation to be sparse, and this allows for character-based indexing without adding a whole bunch of dummies to an arraylist.
It's pretty straightforward to get rid of the duplication (about 50%) in the main loop.
Checking for distinct indices sooner (e.g. when one of the collections is singleton) might speed up execution somewhat.