Scrambled Palindrome Problem- Algorithm and Solution

What the Scrambled Palindrome Problem Actually Is

You have a string. Someone scrambles its characters. Can you rearrange those characters back into a palindrome?

That's the whole problem. No tricks, no hidden complexity. You get "aabbccdd" — can you rearrange it to "abdcba"? Yes. You get "aabbcc" — can you make "abcba"? No, because you don't have enough characters.

The constraint is simple: at most one character can have an odd frequency. Everything else must pair up.

Why This Works

Palindromes read the same forward and backward. Every character on the left side needs a matching character on the right side. That's a pair.

If the string has an even length, every character must pair up. Zero odd-count characters allowed.

If the string has an odd length, exactly one character sits in the middle. That's your one free odd-count character.

More than one odd-count character means you have leftovers that can't be mirrored. The answer is immediately no.

The Algorithm

Here's the entire solution in three steps:

1. Count the frequency of each character
2. Count how many characters have an odd frequency
3. Return true if that count is 0 or 1, false otherwise

That's it. No sorting, no backtracking, no recursion. O(n) time, O(1) or O(k) space depending on your character set.

Python Implementation

def can_form_palindrome(s):
    from collections import Counter
    freq = Counter(s)
    odd_count = sum(1 for count in freq.values() if count % 2 == 1)
    return odd_count <= 1

JavaScript Implementation

function canFormPalindrome(s) {
    const freq = {};
    for (const char of s) {
        freq[char] = (freq[char] || 0) + 1;
    }
    let oddCount = 0;
    for (const count of Object.values(freq)) {
        if (count % 2 === 1) oddCount++;
    }
    return oddCount <= 1;
}

C++ Implementation

bool canFormPalindrome(string s) {
    unordered_map<char, int> freq;
    for (char c : s) freq[c]++;
    int oddCount = 0;
    for (auto& pair : freq) {
        if (pair.second % 2 == 1) oddCount++;
    }
    return oddCount <= 1;
}

Comparing Approaches

Bit Vector Optimization

If you're dealing with lowercase English letters only, you can skip the hash map entirely. Use a 26-bit integer where each bit represents whether a character's count is odd or even. Toggle the bit for each character. At the end, check if at most one bit is set.

bool canFormPalindrome(string s) {
    int bitVector = 0;
    for (char c : s) {
        bitVector ^= (1 << (c - 'a'));
    }
    return bitVector == 0 || (bitVector & (bitVector - 1)) == 0;
}

The final check uses a trick: (x & (x - 1)) == 0 means x has at most one bit set. Clever, but the hash map version is clearer and just as fast.

Common Mistakes

• Forgetting the odd-length case. A single odd-count is allowed. Don't reject strings like "abc" just because they're odd length.
• Overcomplicating with sorting. You don't need to sort to check frequencies. Sorting adds O(n log n) for no reason.
• Using the wrong data structure. A set won't work here. You need counts, not just presence.

Getting Started: Solve It Yourself

1. Pick a language. Python is fastest to write, C++ is fastest to run.
2. Build a frequency map. Loop through the string, increment counts.
3. Count the odds. Iterate through the map, increment a counter for each odd frequency.
4. Return the comparison. odd_count <= 1 is your answer.
5. Test edge cases: empty string, single character, all same characters, all different characters.

Try these examples mentally before coding:

• "" → true (empty string is a palindrome)
• "a" → true
• "ab" → false
• "aaabbb" → true
• "abcabc" → true
• "abcd" → false

When This Problem Appears

You'll see this in technical interviews, competitive programming contests, and coding challenge platforms. The scrambled palindrome check often appears as a sub-problem within larger string manipulation tasks.

It's also a useful building block. If you can check for palindrome-formable strings quickly, you can solve related problems like grouping anagrams, finding the longest palindromic substring, or determining if a string can win a word game.

The solution is straightforward once you internalize the "at most one odd count" rule. Don't overthink it.