Palindromes From a Set of Letters

Medium

You get a set of letters written as a string letters. Rearranging them gives new words of the same length. Return every distinct palindrome you can get by rearranging all the letters of letters (each letter used as many times as it appears). If no palindrome is possible, return an empty list. The answer may be in any order.

Example 1

letters="ttoo" → ['otto', 'toot']

Two t's and two o's make exactly two palindromes.

Example 2

letters="kayak" → ['akyka', 'kayak']

The single "y" goes in the middle; the sides are "ka" or "ak".

Example 3

letters="dog" → []

Three different letters cannot form a palindrome.

Constraints

1 ≤ len(letters) ≤ 16
letters consists of lowercase English letters
There are at most 50,000 distinct palindromes

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table String Backtracking

Similar problems

Keypad Words Medium Does the String Fit the Letter Template Medium Next Time From the Same Digits Medium Count the Tile Sequences Medium Every Rewording of a Sentence Medium

Input

letters="ttoo"

Expected

['otto', 'toot']

Run checks the first 3 tests in your browser. Submit checks all 82 tests on the server, hidden ones included.