Cracking The Coding Interview Together – Problem 1.4: Palindrome Permutation

As always we will follow the format as follows

1. Understand the problem statement together
2. Ask any questions, that you would like to ask the interviewer
3. I would urge you to take your time here and try to come up with your own solution before going forward
4. Think how you would go about solving the problem(you would be talking out loud in front of the actual interviewer)
5. Write code and understand how it works and explain it to your interviewer

Problem statement

Given a string, write a function to check if it is a permutation of a palindrome.
A palindrome is a word or phrase that reads the same forwards and backwards. A permutation is a rearrangement of letters. The palindrome does not need to be limited to just dictionary words.

Example
Input: TactCoa
Output: True — because permutations like "taco cat" or "atco eta" exist.

Analyse the problem statement together

Take a breath and read it carefully. We are not asked to generate permutations, nor to check if the input itself is a palindrome. We are asked whether any permutation of the characters can form a palindrome. Basically the only thing is that we have to figure out is, if it is possible to create a palindrome with this string.

Important clarifications we should note:

• Whitespace and letter case probably don’t matter (example uses mixed case and spaces).
• Non-letter characters? The problem statement is ambiguous here — but it's worth asking.
• Do we consider punctuation? (E.g., commas, periods.) Again — ask the interviewer.
• Are we allowed to modify the string or use extra memory?

Questions for the interviewer

This is important — don’t assume. Speak clearly and ask:

1. Should I ignore spaces and case?
   1. Likely answer: yes — treat letters case-insensitively and ignore spaces.
2. What characters should we consider?
   1. Letters only, all ASCII, or full Unicode? For the book problem, assume lowercase a–z unless stated otherwise.
3. Can the input be null or empty?
   1. We should ask this and handle it; typical answer: yes, it can be, and usually we return true for empty / null depending on policy.
4. Are we allowed to use extra data structures?
   1. Usually yes for the basic solution; later we can optimize.
5. What language/format should I present?
   1. Working code is preferred in the previous posts — we’ll give Java code.

Now assume we got answers (adjust if interviewer answers differently):

• Ignore spaces. Case-insensitive.
• Consider letters a–z.
• Null → treat as true? (Commonly: if both are null or empty — return true; but here we only have one input, so null could return true or false depending on policy — I usually ask to treat null as true if we define empty string as palindrome permutation. For safety, ask interviewer.)
• Allowed to use extra storage for the first solution.

Think about the Solution

Pause for a couple of minutes and think. Form the intuition. Don’t rush into code. Try to reason in plain language:

• What does it take to form a palindrome from characters?
  In a palindrome, characters appear in pairs mirrored around the center. If the length is odd, exactly one character can remain unmatched (the center). If the length is even, no character can be unmatched.
• So the frequency property is the core:
  For the string to be a permutation of a palindrome, at most one character may have an odd count and the rest must have even counts.

Steps

1. Normalize the string: remove spaces and convert to lowercase.
2. Count frequencies of relevant characters (a–z).
   • Option A: use a hash map / int array.
   • Option B: use a bit vector to track odd/even counts (flip bit on each occurrence).
3. Check how many characters have odd counts.
   • If > 1 → return false.
   • Else → return true.

Also mention edge cases:

• Empty string → true (palindrome).
• String with one character → true.
• String with non-letter characters (if allowed) — need to include/exclude based on interviewer direction.

I think now you have a good understanding of how to tackle this problem and you have formed a solid intuition around it. Now the last step that is left is to write code and explain it to your Interviewer.

Write code and explain

Solution 1 - Frequency array

We assume letters are a–z after normalization.

public static boolean isPalindromePermutation(String s) {
    if (s == null) return true; // confirm with interviewer; treating null as true for empty-case parity

    // Normalize: lowercase and ignore non-letters (spaces/punctuation)
    StringBuilder sb = new StringBuilder();
    for (char ch : s.toCharArray()) {
        if (Character.isLetter(ch)) {
            sb.append(Character.toLowerCase(ch));
        }
    }
    String normalized = sb.toString();

    // Count frequencies for a-z
    int[] counts = new int[26];
    for (char ch : normalized.toCharArray()) {
        counts[ch - 'a']++;
    }

    // Check that at most one character has an odd count
    boolean foundOdd = false;
    for (int count : counts) {
        if ((count & 1) == 1) {
            if (foundOdd) {
                return false;
            }
            foundOdd = true;
        }
    }
    return true;
}

Explain to interviewer while coding:

• We normalized the input, so spaces and case don't matter.
• We used a fixed-size array — constant space (26 ints).
• We loop over the string once (two passes effectively, but linear overall).
• The final loop checks odd counts; we early-return false if we find more than one odd.

Complexity:

• Time: O(n) where n is the length of the string (normalization + count pass).
• Space: O(1) — 26 sized array, constant.

Solution 2 — HashMap

If the domain includes Unicode or other characters, we can use a Map<Character,Integer>.

public static boolean isPalindromePermutationMap(String s) {
    if (s == null) return true;

    Map<Character, Integer> freq = new HashMap<>();
    for (char ch : s.toCharArray()) {
        if (!Character.isLetter(ch)) continue;
        char lower = Character.toLowerCase(ch);
        freq.put(lower, freq.getOrDefault(lower, 0) + 1);
    }

    int oddCount = 0;
    for (int count : freq.values()) {
        if ((count & 1) == 1) {
            oddCount++;
            if (oddCount > 1) return false;
        }
    }
    return true;
}

Complexity:

• Time: O(n)
• Space: O(k) where k is number of distinct relevant characters (up to n).

When to prefer: use this if you must support more than ASCII letters or if the interviewer clarifies a broader character set.

Personally I like this solution much better, cleaner and easier to explain and it works as good as the previous solution in terms of time complexity. Even though it has a slightly increased space complexity it covers that with easier implementation and support for broader character set.

Final Thoughts

• This problem demonstrates the power of finding the invariant — here, the odd-count invariant — instead of brute-force permutations.
• It’s an example where a small structural observation reduces the problem to a quick linear pass.
• In interviews, highlight your clarifications, show the plan (normalization → counting → odd-check), then code cleanly and test a couple of cases live.

Happy Coding!