In this article, we will see Java algorithm to find out if a String is a permutation of a palindrome.

 
Palindrome is a word or phrase that is the same when you traverse from beginning or end.

For example ,

“race car”, “anna”, “abcba” are palindromes.

Now, the String “car race” is a permutation of “race car” which is a palindrome.

So, the program should return true if “aabbc” is entered.

car race -> true
abcde -> false

Program

For a word to be palindrome, it should have the same character when traversed from beginning and end..so, it should be repeated atleast twice.
If the word has odd number of total characters, it will a single character in the middle.

So, we can check the length of the String and if its even, check if it has 2 off each character or not.
If the length is odd, we need to check if it has 2 of each character, and only one character that isn’t repeated.
 

import java.util.HashMap;
import java.util.Map;

public class SomeProgram {

  public static void main(String[] args) {
    String str = "car race";
    System.out.println(checkPermutationOfPalindrome(str));
  }

  private static boolean checkPermutationOfPalindrome(String str) {
    char[] arr = str.replaceAll("[\\s]", "").toLowerCase().toCharArray();
    Map<Character, Integer> map = new HashMap<Character, Integer>();

    for (char ch : arr) {
      int count = 1;
      if (map.containsKey(ch)) {
        count = map.get(ch);
        count++;
      }
      map.put(ch, count);
    }
    
    boolean foundOdd = false;
    // return false if more than one odd found
    for (char ch : map.keySet()) {
      int value = map.get(ch);
      System.out.println("" + ch + ":" + value);
      if (value % 2 == 1) {
        if (foundOdd) {
          return false;
        }
        foundOdd = true;
      }
    }
    return true;
  }
}

Output :

a:2
r:2
c:2
e:1
true

© 2018, www.topjavatutorial.com. All rights reserved. On republishing this post, you must provide link to original post