Tag Archives: Characters

Solutions, Technical Interviews

Permuting a String to Make a Palindrome

1 Comment

Objective

Given a string of characters, determine whether or not some permutation of the string creates a palindrome.

Observations

  1. A palindrome is a word that reads the same forward as it does backward.
  2. 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);
	}
}