Objective
Given a string of characters, determine whether or not some permutation of the string creates a palindrome.
Observations
- A palindrome is a word that reads the same forward as it does backward.
- We can use a sequence of characters to build a palindrome if either of the following conditions are satisfied:
- Each character occurs an even number of times.
- Each character occurs an even number of times except for one character.
Code
import java.util.*;
class Solution {
/**
* @param String s The string to check
* @return true if the string can be permuted into a palindrome
**/
public static boolean hasPalindromicPermutation(String s) {
// Create a set to hold unmatched characters
Set unmatched = new HashSet();
for (int i = 0; i < s.length(); i++) {
// The current character
char c = s.charAt(i);
// If the character exists in the set, remove it
if (unmatched.contains(c)) {
unmatched.remove(c);
}
// Character is unmatched, add it to the set
else {
unmatched.add(c);
}
}
// For the string to be a palindrome, only 0 or 1 character can be unmatched
return (unmatched.size() < 2);
}
}
One thought on “Permuting a String to Make a Palindrome”