Advertisement
JeffGrigg

Untitled

Dec 25th, 2017
264
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5 4.10 KB | None | 0 0
  1. import java.util.*;
  2.  
  3. public class Solution {
  4.  
  5.     public static void main(String args[]) {
  6.         Scanner scan = new Scanner(System.in);
  7.         String myString = scan.next();
  8.  
  9.         String result = makeBeautiful(myString);
  10.  
  11.         //if no one of the reordered permutation gives a beautiful string print NO
  12.         if (result == null) {
  13.             System.out.println("NO");
  14.         } else {
  15.             System.out.println("YES");
  16.             System.out.println(result);
  17.         }
  18.     }//end of main
  19.  
  20.     public static String makeBeautiful(String myString) {
  21.         //odd string cannot be beautiful
  22.         if (myString.length() % 2 != 0) {
  23.             return null;
  24.         }
  25.  
  26.         // count the number of maximum occurring character if it is more than String length/2
  27.         //so it cannot be reordered to be beautiful
  28.         int count[] = new int[256];
  29.         int len = myString.length();
  30.         for (int i = 0; i < len; i++)
  31.             count[myString.charAt(i)]++;
  32.         int max = -1;  // Initialize max count
  33.         for (int i = 0; i < len; i++) {
  34.             if (max < count[myString.charAt(i)]) {
  35.                 max = count[myString.charAt(i)];
  36.             }
  37.         }
  38.         if (max > (len / 2)) {
  39.             return null;
  40.         }
  41.  
  42.         String result = check(myString);//check if beautiful
  43.  
  44.         String newString = frequencySort(myString);//sort the string frequency Sort.
  45.         if (result == null) {
  46.             result = check(newString); // check again
  47.         }
  48.  
  49.         if (result == null) {
  50.             String sub1 = newString.substring(0, newString.length() / 2);
  51.             String sub2 = newString.substring(newString.length() / 2);
  52.             String sub3 = sub2 + sub1;
  53.             result = check(sub3);// check again
  54.         }
  55.  
  56.         // if not try to reorder the string to be beautiful
  57.         if (result == null) {
  58.             result = permutation(newString);
  59.         }
  60.  
  61.         return result;
  62.     }
  63.  
  64.     public static String check(String myString) {
  65.         int counter = 0;
  66.         String str2 = ""; // find reverse
  67.         for (int i = myString.length() - 1; i >= 0; i--) {
  68.             str2 = str2 + myString.charAt(i);
  69.         }
  70.         for (int i = 0; i < myString.length(); i++) {//check if beautiful
  71.             if (str2.charAt(i) != myString.charAt(i)) {
  72.                 counter++;
  73.             } else break;
  74.         }
  75.         if (counter == myString.length()) {
  76.             return str2;
  77.         }
  78.         return null;
  79.     }
  80.  
  81.     public static String frequencySort(String s) {
  82.         Map<Character, Integer> map = new HashMap<>();
  83.         for (char c : s.toCharArray()) {
  84.             if (map.containsKey(c)) {
  85.                 map.put(c, map.get(c) + 1);
  86.             } else {
  87.                 map.put(c, 1);
  88.             }
  89.         }
  90.         List<Character>[] bucket = new List[s.length() + 1];
  91.         for (char key : map.keySet()) {
  92.             int frequency = map.get(key);
  93.             if (bucket[frequency] == null) {
  94.                 bucket[frequency] = new ArrayList<>();
  95.             }
  96.             bucket[frequency].add(key);
  97.         }
  98.         StringBuilder sb = new StringBuilder();
  99.         for (int pos = bucket.length - 1; pos >= 0; pos--) {
  100.             if (bucket[pos] != null) {
  101.                 for (char num : bucket[pos]) {
  102.                     for (int i = 0; i < map.get(num); i++) {
  103.                         sb.append(num);
  104.                     }
  105.                 }
  106.             }
  107.         }
  108.         return sb.toString();
  109.     }
  110.  
  111.     public static String permutation(String input) {
  112.         return permutation("", input);
  113.     }
  114.  
  115.     private static String permutation(String perm, String word) {
  116.         String result = null;
  117.         if (word.isEmpty()) {
  118.             String newPer = perm + word;
  119.             result = check(newPer);
  120.         } else {
  121.             for (int i = word.length() / 2; i < word.length() && result == null; i++) {
  122.                 result = permutation(perm + word.charAt(i), word.substring(0, i) + word.substring(i + 1, word.length()));
  123.             }
  124.         }
  125.         return result;
  126.     }
  127.  
  128. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement