FastPrepPalindrome-Rearrangeable Pairs
Problems/Palindrome-Rearrangeable Pairs

Palindrome-Rearrangeable Pairs

Expedia logoExpedia● EasyINTERNOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The report describes a variant of a well-known palindrome pairs problem. Given an array of strings, find which pairs are complement. A pair is complement if, after you join the two strings, you can rearrange the result into a palindrome.

The report gives no examples or limits and does not say how to write the answer. Here, you list every complement pair as positions [i, j], counting from 0 with i < j, sorted by i and then by j. Each pair appears once. Equal strings at different positions make separate pairs. Strings use only lowercase English letters. The answer format, these rules, the limits, the examples, and the function shape are our choices, not from the report.

Our version is about 85% the same as the reported question.

You are given an array of strings words. Two positions i and j with i < j form a complement pair when you can join words[i] and words[j], put the letters of the joined string in any order you like, and get a palindrome.

A palindrome reads the same forwards and backwards.

Return every complement pair as [i, j], following these rules:

  • Positions start at 0.
  • Inside a pair, the smaller position comes first.
  • Sort the pairs by i, then by j, both from small to large.
  • Each pair of positions appears once, and a position cannot pair with itself.
  • Pairs are told apart by position, so equal strings at different positions make their own pairs.
  • If there are no complement pairs, return an empty list.

Function

findPalindromeRearrangeablePairs(words: String[]) → int[][]

Examples

Example 1

words = ["ab","ba","c"]return = [[0,1]]

Joining ab and ba gives abba, which already reads the same both ways. Joining either one with c gives three different letters, each used once, so no order of those letters is a palindrome. Only the pair of positions 0 and 1 qualifies.

Example 2

words = ["a","aa","b"]return = [[0,1],[1,2]]

The pair at positions 0 and 1 gives aaa. The pair at positions 1 and 2 gives aab, which can become aba. The pair at positions 0 and 2 gives ab, and no order of it is a palindrome.

Example 3

words = ["abc","abc","abc"]return = [[0,1],[0,2],[1,2]]

All three strings are equal, but they sit at different positions, so each pair of positions is listed. Each pair joins to abcabc, which can become abccba. No position pairs with itself.

Example 4

words = ["abc","ab","d"]return = [[0,1]]

The pair abc and ab gives abcab, which has two a, two b, and one c, so it can become abcba. Neither string can become a palindrome alone, but the pair can. Each pair with d has too many letters used an odd number of times: abcd has four and abd has three.

Example 5

words = ["b","aa","b","a"]return = [[0,1],[0,2],[1,2],[1,3]]

Sort by the first position, then by the second. Position 0 (b) pairs with positions 1 and 2. Position 1 (aa) pairs with positions 2 and 3. Position 2 (b) and position 3 (a) give ba, which does not qualify, and neither do positions 0 and 3.

Example 6

words = ["racecar"]return = []

There is only one string, so there is no pair, and the result is an empty list. A string cannot pair with itself, even though racecar is a palindrome.

Constraints

  • 1 <= words.length <= 60
  • 1 <= words[i].length <= 200
  • words[i] contains only lowercase English letters.

More Expedia Online Assessment questions

  • Balanced NumbersOA · Seen Aug 2026
  • REST API: Discounted PriceOA · Seen Aug 2026
  • Maximum Team SizeOA · Seen Mar 2026
  • Per-Domain Request LimiterOA · Seen Oct 2025
  • Count Equal-Frequency SubsequencesOA · Seen Mar 2025
  • Count Increasing Stock PeriodsOA · Seen Mar 2025
  • Get Minimum StepsOA · Seen Oct 2024
  • Rank Songs by PopularityOA · Seen Oct 2024
  • Calculate the SumOA · Seen Oct 2024
  • Get Maximum EfficiencyOA · Seen Oct 2024

Similar questions at other companies

  • Count User Mentions in Chat MessagesRamp · OARamp interview questions
  • Find Words That Can Be Formed by CharactersTabaPay · OA
  • Word Frequency Counts in Alphabetical OrderAbridge · OAAbridge interview questions
  • Customer Signer ScreeningState Farm · OA
  • String-Pair Frequency SimilarityIBM · OAIBM interview questions
  • Number-Character Bijective MappingAdobe · OAAdobe interview questions
  • Unique Difference PatternMicrosoft · OAMicrosoft interview questions
  • Filter Transaction Logs and Calculate Reliability MetricsStripe · OAStripe interview questions
  • Nonzero Totals by NameEPAM · OAEPAM interview questions
  • Palindrome PermutationRippling · OARippling interview questions

Interview reports that mention this question

  • Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)

Expedia interview experiences

  • Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
  • Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
  • Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
  • Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
  • Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public int[][] findPalindromeRearrangeablePairs(String[] words) {
        // Write your code here.
    }
}
Checking account…