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

To solve this problem and check whether two strings are anagrams you don't actually need to generate every single permutation of the source string and then match it against the second one. What you can do instead, is count the frequency of each character in the first string, and then verify whether the same frequency applies for the second string.

The solution above requires one pass for each string, hence Θ(n) time complexity. In addition, you need auxiliary storage for counting characters which is Θ(1) space complexity. These are asymptotically tight bounds.

Answer 2

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.

Answer 3

You can first get arrays of characters from these strings, then sort them, and then compare the two sorted arrays. This method works with both regular characters and surrogate pairs.

public static void main(String[] args) {
    System.out.println(isAnagram("ABCD", "DCBA")); // true
    System.out.println(isAnagram("", "")); // true
}

static boolean isAnagram(String a, String b) {
    // invalid incoming data
    if (a == null || b == null
            || a.length() != b.length())
        return false;

    char[] aArr = a.toCharArray();
    char[] bArr = b.toCharArray();

    Arrays.sort(aArr);
    Arrays.sort(bArr);

    return Arrays.equals(aArr, bArr);
}

---

^{See also: Check if one array is a subset of the other array - special case}