Determining if two strings are anagrams

Question

Two strings are said to be anagrams of each other if the letters of one string may be rearranged to make the other string. For example, the words 'elvis' and 'lives' are anagrams.

In this problem you’ll be given two strings. Your job is to find if the two strings are anagrams of each other or not. If they are not anagrams then find the lexicographically smallest palindrome (in lowercase alphabets) that may be appended to the end of either one of the two strings so that they become anagrams of each other.

The lower and upper case letters are considered equivalent. The number of spaces or any other punctuation or digit is not important.

One string is called lexicographically smaller than another if, at the first position where they differ the first one has smaller alphabet. For example, the strings 'hello' and 'herd' first differ at the third alphabet; 'l' is smaller than 'r', so 'hello' is lexicographically smaller than 'herd'.

A Palindrome is a string that is the same when read forward or backward. For example, the string 'bird rib' is a palindrome, whereas 'hello' is not.

Input:

The first line of the input contains a number T, the number of test cases. T test cases follow. Each test case consists of two lines, one string in each line.

Output:

For each test case output a single line. Print ‘YES’ (without the quotes) if the two strings are anagrams of each other. If they are not, then print the lexicographically smallest palindromic string as discussed above. If no such string exists, then print ‘NO LUCK’ (without the quotes).

Constraints:

\$1 \le T \le 100\$

\$1 \le \text{length of the strings} \le 100\$

• Input file
• Matched output file

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/*
 * Created by ankur on 20-10-2015.
 */
public class Anagrams {

    private static final String NO_LUCK = "NO LUCK";
    private static final String YES = "YES";
    public static void main(String... str) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int totalInput = Integer.parseInt(reader.readLine());
        StringBuilder output = new StringBuilder(totalInput);
        while (totalInput > 0) {
            totalInput--;
            String inputString1 = reader.readLine().trim().toLowerCase();
            String inputString2 = reader.readLine().trim().toLowerCase();
            String result = isAnagramPossible(inputString1, inputString2);
            output.append(result);
            output.append("\n");
        }
        System.out.println(output);
    }

    private static String isAnagramPossible(String a, String b){
        int[] returnedArray = isAnagram(a,b);
        /*System.out.println(returnedArray.length);
        for (int i:returnedArray){
            System.out.println(i);
        }*/
        int sum = 0,oddCount = 0;
        for (int i:returnedArray) {
            if ((i & 1) != 0){
                oddCount += 1;
            }
            sum += i;
        }
        if(sum == 0){
            return YES;
        }

        // Handling summing 1 case otherwise will get
        // java.lang.ArrayIndexOutOfBoundsException: 0 in
        // constructPalindrome function
        else if(sum == 1){
            for (int i= 0; i < 26; i++){
                if (returnedArray[i] == 1){
                    return String.valueOf((char)('a' + i));
                }
            }
        }
        else if(oddCount > 1){
            return NO_LUCK;
        }
        System.out.println("Test");
        String palindromeAdd = constructPalindrome(returnedArray);



       return palindromeAdd;
}

    /*
    Constructing the palindrome string
     */
    private static String constructPalindrome(int[] charFrequenciesDiff){
        Character[] palindrome;
        System.out.println("Test");
        List<Character> characterList= new ArrayList<>();
        char midChar = ' ';
        boolean handleOdd = false;
        for (int i = 0; i< 26; i++ ){
            int total=charFrequenciesDiff[i];
            if((total & 1) == 1){
                handleOdd = true;
                total -= 1;
                midChar = (char)('a' + i);
            }
            while (total>0){
                total--;
                characterList.add((char)('a' + i)); //
            }
        }

        palindrome = characterList.toArray(new Character[characterList.size()]);
        int palindromeLen = palindrome.length;
        Arrays.sort(palindrome);
        if (palindromeLen == 1 || palindrome[0] == palindrome[palindromeLen - 1]){
            String str1= Arrays.toString(palindrome);
            str1 = str1.substring(1, str1.length()-1).replaceAll(", ", "");
            return str1 ;
        }

        StringBuilder sb = new StringBuilder();



            int i =0;
            while(i < palindromeLen){
                sb.append(palindrome[i]);
                i += 2;
            }
            StringBuilder reverse = new StringBuilder(sb);

        // Handle Odd case.
        if(handleOdd){
                sb.append(midChar);
            }
            sb.append(reverse.reverse());
            return sb.toString();

    }

    private static int[] isAnagram(String a, String b){
        int[] returnArray = new int[26];
        char[] a1 = new char[26];
        char[] a2 = new char[26];
        Arrays.fill(returnArray,0);
        Arrays.fill(a1, ' ');
        Arrays.fill(a2, ' ');
        char[] aArray = a.toCharArray();
        char[] bArray = b.toCharArray();
        for (int i = 0, len = a.length(); i < len; i++ ){
            if(Character.isAlphabetic(aArray[i])) {
                int pos = (int) aArray[i] - (int) 'a';
                a1[pos] += 1;
            }
        }

        for (int i = 0, len = b.length(); i < len; i++ ){
            if(Character.isAlphabetic(bArray[i])) {
                int pos = (int) bArray[i] - (int) 'a';
                a2[pos] += 1;
            }
        }

        int j =0;
        boolean is_true = true;

        while (j < 26 && is_true){
            if (a1[j] == a2 [j]){
                j = j+ 1;
            }
            else {
                is_true = false;
            }
        }

        if (!is_true){
            for (int i = 0; i < 26; i++){
                returnArray[i] = Math.abs(a1[i] - a2[i]);
            }
        }
        return returnArray;
    }
}

Output time: 0.1619sec

How can I further improve the performance of this code in terms of time? Avoid repetitions if I did it somewhere. Also, lambdas elude me.

Answer 1

The first thing that pops in my mind is the naming you used. For example, from a method called isAnagramPossible I'd expect to receive a bool and not a string. The same from isAnagram.

In the isAnagram method the returnArray variable should be renamed IMO as the name is not so meaningful. The same regarding is_true.

Also, commented code is only confusing. I'd remove it.

In addition:

    for (int i = 0, len = a.length(); i < len; i++ ){
        if(Character.isAlphabetic(aArray[i])) {
            int pos = (int) aArray[i] - (int) 'a';
            a1[pos] += 1;
        }
    }

    for (int i = 0, len = b.length(); i < len; i++ ){
        if(Character.isAlphabetic(bArray[i])) {
            int pos = (int) bArray[i] - (int) 'a';
            a2[pos] += 1;
        }
    }

is repeated code (the two cycles are almost the same) and could be transformed in a method.

Other things seem ok.

Answer 2

Method names

private static String isAnagramPossible(String a, String b) { ... }

private static int[] isAnagram(String a, String b) { ... }

The Java convention for method names starting with is suggests that they should return a boolean value. You may want to consider renaming them as such:

private static String check(String a, String b) { ... }

private static int[] getDifference(String a, String b) { ... }

Checking for differences

I think the (renamed) getDifference(String, String) method can be improved. Currently, there's just too much 'steps' to create the necessary int[] arrays, loop through the Strings to populate said arrays, and them computing the differences. Instead of diving straight to int[] arrays, you can consider constructing a 'letter map' first, get the differences, and then generate the desired int[] array result. This is assuming you still want to stick to that type for the constructPalindrome() method.

private static int[] getDifference(String a, String b) {
    Map<Integer, Long> map = toLetterMap(a);
    toLetterMap(b).forEach((i, c) -> map.merge(i, c, (x, y) -> Math.abs(x - y)));
    int[] result = new int[26];
    map.forEach((i, c) -> result[i - 'a'] = c.intValue());
    return result;
}

private static Map<Integer, Long> toLetterMap(String v) {
    return v.chars().filter(Character::isLetter).map(Character::toLowerCase).boxed()
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
}

For the toLetterMap(String) method:

1. Call String.chars() to get an IntStream of 'characters'.
2. Filter only for letters using Character.isLetter(int), and then for consistency toLowerCase(int) as well, so you may want to do all the String normalization here instead of your main() method.
3. Convert the IntStream to a Stream<Integer> using boxed(), so that we can do a groupingBy() to get our 'letter map'.

For the getDifference(String, String) method:

1. Call toLetterMap(String) on the first String to get an initial Map object map.
2. forEach() of the Map entries from the second call to toLetterMap(String), we merge() them into map accordingly.
3. Finally, create the int[] array and populate it, as your original handling.

Handling edge cases

// Handling summing 1 case otherwise will get
// java.lang.ArrayIndexOutOfBoundsException: 0 in
// constructPalindrome function
else if(sum == 1) { ... }

I think this might be better handled in the constructPalindrome method then, so that the method body of the (renamed) check(String, String) gets the difference in Strings from getDifference(String, String), and calls constructPalindrome(int[]) if there are differences. There is thus no special handling 'dangling' in the method.

Miscellaneous

System.out.println("Test");

You don't need that. :) You may want to pay attention to commented code (delete them as early as possible?) and also to redundant empty lines.