Round E 2021 Google Kick Start Shuffled Anagrams Problem | Java | Know About

Problem

Let S be a string containing only letters of the English alphabet. An anagram of S is any string that contains exactly the same letters as S (with the same number of occurrences for each letter), but in a different order. For example, the word kick has anagrams such as kcik and ckki.

Now, let S[i] be the i-th letter in S. We say that an anagram of S, A, is shuffled if and only if for all i, S[i]≠A[i]. So, for instance, kcik is not a shuffled anagram of kick as the first and fourth letters of both of them are the same. However, ckki would be considered a shuffled anagram of kick, as would ikkc.

Given an arbitrary string S, your task is to output any one shuffled anagram of S, or else print IMPOSSIBLE if this cannot be done.

Input

The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of one line, a string of English letters.

Output

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is a shuffled anagram of the string for that test case, or IMPOSSIBLE if no shuffled anagram exists for that string.

In test case #1, tarts is a shuffled anagram of start as none of the letters in each position of both strings match the other. Another possible solution is trsta (though you only need to provide one solution). However, in test case #2, there is no way of anagramming jjj to form a shuffled anagram, so IMPOSSIBLE is printed instead.


PROGRAM

import java.util.*; public class Solution { public static void main(String[] args) throws Exception{ Scanner sc = new Scanner(System.in); int t = sc.nextInt(); for(int i=1; i<=t; i++) { String n = sc.next(); Character a[] = new Character[n.length()]; for(int j=0; j<n.length(); j++) { a[j] = n.charAt(j); } System.out.printf("Case #%d: %s\n",i,str(n,a)); } } private static Object str(String n, Character[] a) { int count=0; for(int m=0; m<n.length(); m++) { int tempcount = 0; for(int l=0; l<n.length(); l++) { if(a[m] == a[l]) tempcount++; } if(tempcount > count) { count = tempcount; } } if(count > n.length()/2) { return "IMPOSSIBLE"; } return again(n); } private static String again(String n) { char a[] = n.toCharArray(); for (int i = 0; i < a.length; i++) { for (int j = 0; j < a.length; j++) { if (a[i] != a[j] && a[i] != n.charAt(j) && a[j] != n.charAt(i)) { char tmp = a[i]; a[i] = a[j]; a[j] = tmp; break; } } } return new String(a); } }

Here is the link for Google KickStart Round A 2020 Plates problem using JAVA.