FastPrep
Problem

Count Palindromic Concatenation Pairs

OA
See Salesforce online assessment and hiring insights

You are given a list of lowercase strings words.

Count the number of index pairs (i, j) such that i < j and some permutation of the concatenation words[i] + words[j] can form a palindrome.

A string can be rearranged into a palindrome if at most one character has an odd frequency.

Examples
01 · Example 1
words = ["ab","ba","abc","c"]
return = 3

The valid pairs are (0,1), (0,2), and (1,2).

02 · Example 2
words = ["aa","bb","ab"]
return = 1

Only "aa" + "bb" can be rearranged into a palindrome.

Constraints
  • 1 <= words.length
  • Total length of all strings is at most 3 * 10^5.
  • words[i] contains only lowercase English letters.
More Salesforce problems
drafts saved locally
public long countPalindromicConcatenationPairs(String[] words) {
  // write your code here
}
words["ab","ba","abc","c"]
expected3
sign in to submit