How to handle the time complexity for permutation of strings during anagrams search?

Question

I have a program that computes that whether two strings are anagrams or not. It works fine for inputs of strings below length of 10. When I input two strings whose lengths are equal and have lengths of more than 10 program runs and doesn't produce an answer .

My concept is that if two strings are anagrams one string must be a permutation of other string.

This program generates the all permutations from one string, and after that it checks is there any matching permutation for the other string. In this case I wanted to ignore cases. It returns false when there is no matching string found or the comparing strings are not equal in length, otherwise returns true.

public class Anagrams {
    static ArrayList<String> str = new ArrayList<>();

    static boolean isAnagram(String a, String b) {
        // there is no need for checking these two
        // strings because their length doesn't match
        if (a.length() != b.length())
            return false;

        Anagrams.permute(a, 0, a.length() - 1);

        for (String string : Anagrams.str)
            if (string.equalsIgnoreCase(b))
                // returns true if there is a matching string
                // for b in the permuted string list of a
                return true;
        // returns false if there is no matching string
        // for b in the permuted string list of a
        return false;
    }

    private static void permute(String str, int l, int r) {
        if (l == r)
            // adds the permuted strings to the ArrayList
            Anagrams.str.add(str);
        else {
            for (int i = l; i <= r; i++) {
                str = Anagrams.swap(str, l, i);
                Anagrams.permute(str, l + 1, r);
                str = Anagrams.swap(str, l, i);
            }
        }
    }

    public static String swap(String a, int i, int j) {
        char temp;
        char[] charArray = a.toCharArray();
        temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
        return String.valueOf(charArray);
    }
}

1. I want to know why can't this program process larger strings

2. I want to know how to fix this problem

Can you figure it out?

Answer 1

you're doing it in very expensive way and the time complexity here is exponential because your'e using permutations which requires factorials and factorials grow very fast , as you're doing permutations it will take time to get the output when the input is greater than 10.

11 factorial = 39916800 12 factorial = 479001600 13 factorial = 6227020800

and so on...

So don't think you're not getting an output for big numbers you will eventually get it

If you go something like 20-30 factorial i think i will take years to produce any output , if you use loops , with recursion you will overflow the stack.

fact : 50 factorial is a number that big it is more than the number of sand grains on earth , and computer surrender when they have to deal with numbers that big.

That is why they make you include special character in passwords to make the number of permutations too big that computers will not able to crack it for years if they try every permutations , and encryption also depends on that weakness of the computers.

So you don't have to and should not do that to solve it (because computer are not good very at it), it is an overkill

why don't you take each character from one string and match it with every character of other string, it will be quadratic at in worst case.

And if you sort both the strings then you can just say

string1.equals(string2)

true means anagram

false means not anagram

and it will take linear time,except the time taken in sorting.