Palindrome-Rearrangeable Pairs
Updated
Problem statement
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 byj, 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 <= 601 <= words[i].length <= 200words[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 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)