CODEWITHSUNDEEP
javaoptimization
reaper1
reaper1

Reputation: 153

Optimal Solution for the following code to reduce running time

The following code is used to take a string input and find if any of its permutation are palindrome. The code is taking o(n) time. I was hoping for a better solution.

public class Solution {

    public static void main(String[] args) {
        Scanner myScan = new Scanner(System.in);
        String str = myScan.nextLine();

        String a = "NO";
        permutation("", str);
        System.out.println(a);
        // Assign ans a value of YES or NO, depending on whether or not inputString satisfies the required condition
        myScan.close();
    }

    private static void permutation(String prefix, String str) {
        int n = str.length();
        String an = "NO";
        if (n == 0) {
            System.out.println(prefix);
            StringBuffer sb = new StringBuffer(prefix).reverse();
            String str1 = sb.toString();

            if (prefix.equals(str1)) {
                an = "YES";
                System.out.println(an);
                System.exit(0);
            }

        } else {
            for (int i = 0; i < n; i++) {
                permutation(prefix + str.charAt(i),
                  str.substring(0, i) + str.substring(i + 1));
            }
        }
    }
}

Upvotes: 3

Views: 97

Answers (1)

tobias_k
tobias_k

Reputation: 82889

(This looks a bit like homework, or a Java beginner's private excercise, so I'd prefer not to give you full code but just the idea, or algorithm, so you can come up with the actual implementation yourself.)

There is no need to enumerate all the permutations and see whether one of them is a palindrome. All you need to do is to count all the letters in the word and see if there is at most one letter that has an odd number of occurences. Take for example the palindrome racecar. It can be seen as having three parts: rac e car. The letters in the first and third part are the same, so each of those letters has to have an even count. The second part has just one kind of letter, but it can be repeated any number of times.

So, the basic algorithm is like this:

  • create a dictionary, map, for counting the letters, e.g. HashMap<String, Integer> in Java
  • for each individual character in the word, increase its count in the map by one
  • create a counter for odd-numbered letters, e.g. int odd_letters
  • for each character in the map, check whether its count is odd, and if so, increase the odd_letters counter by one
  • if the odd_letters counter is smaller or equal to one, return true, otherwise return false

If you also need to know the actual palindromic permutation, if there is any, you can easily construct one from the counts map.

Let's say our word is racecar. Counts are {a: 2, c: 2, e: 1, r: 2}

  • for each even-numbered letter, concatenate half of those letters' number, in any order, e.g. acr
  • add the odd-numbered letter in the middle, if any, as often as it was counted: acr e
  • finally, add the first part again, in reverse order: acr e rca

(Of course, racecar in itself already is a palindrome, but that does not matter; it's just easier to find an actual palindromic word than a word with a palindromic permutation.)

Finally, note that the complexity of your code is not O(n) (assuming that n is the length of the string). You are generating all the permutations, so this alone has to be at least O(n!), as there are n! permutations.

Upvotes: 2

Related Questions