Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class Solution {
- public static void main(String args[]) {
- Scanner scan = new Scanner(System.in);
- String myString = scan.next();
- String result = makeBeautiful(myString);
- //if no one of the reordered permutation gives a beautiful string print NO
- if (result == null) {
- System.out.println("NO");
- } else {
- System.out.println("YES");
- System.out.println(result);
- }
- }//end of main
- public static String makeBeautiful(String myString) {
- //odd string cannot be beautiful
- if (myString.length() % 2 != 0) {
- return null;
- }
- // count the number of maximum occurring character if it is more than String length/2
- //so it cannot be reordered to be beautiful
- int count[] = new int[256];
- int len = myString.length();
- for (int i = 0; i < len; i++)
- count[myString.charAt(i)]++;
- int max = -1; // Initialize max count
- for (int i = 0; i < len; i++) {
- if (max < count[myString.charAt(i)]) {
- max = count[myString.charAt(i)];
- }
- }
- if (max > (len / 2)) {
- return null;
- }
- String result = check(myString);//check if beautiful
- String newString = frequencySort(myString);//sort the string frequency Sort.
- if (result == null) {
- result = check(newString); // check again
- }
- if (result == null) {
- String sub1 = newString.substring(0, newString.length() / 2);
- String sub2 = newString.substring(newString.length() / 2);
- String sub3 = sub2 + sub1;
- result = check(sub3);// check again
- }
- // if not try to reorder the string to be beautiful
- if (result == null) {
- result = permutation(newString);
- }
- return result;
- }
- public static String check(String myString) {
- int counter = 0;
- String str2 = ""; // find reverse
- for (int i = myString.length() - 1; i >= 0; i--) {
- str2 = str2 + myString.charAt(i);
- }
- for (int i = 0; i < myString.length(); i++) {//check if beautiful
- if (str2.charAt(i) != myString.charAt(i)) {
- counter++;
- } else break;
- }
- if (counter == myString.length()) {
- return str2;
- }
- return null;
- }
- public static String frequencySort(String s) {
- Map<Character, Integer> map = new HashMap<>();
- for (char c : s.toCharArray()) {
- if (map.containsKey(c)) {
- map.put(c, map.get(c) + 1);
- } else {
- map.put(c, 1);
- }
- }
- List<Character>[] bucket = new List[s.length() + 1];
- for (char key : map.keySet()) {
- int frequency = map.get(key);
- if (bucket[frequency] == null) {
- bucket[frequency] = new ArrayList<>();
- }
- bucket[frequency].add(key);
- }
- StringBuilder sb = new StringBuilder();
- for (int pos = bucket.length - 1; pos >= 0; pos--) {
- if (bucket[pos] != null) {
- for (char num : bucket[pos]) {
- for (int i = 0; i < map.get(num); i++) {
- sb.append(num);
- }
- }
- }
- }
- return sb.toString();
- }
- public static String permutation(String input) {
- return permutation("", input);
- }
- private static String permutation(String perm, String word) {
- String result = null;
- if (word.isEmpty()) {
- String newPer = perm + word;
- result = check(newPer);
- } else {
- for (int i = word.length() / 2; i < word.length() && result == null; i++) {
- result = permutation(perm + word.charAt(i), word.substring(0, i) + word.substring(i + 1, word.length()));
- }
- }
- return result;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement