How to check if two strings are "brother string"?

If string A and string B contain the same characters, they are called "brother string".

for example: "abc" and "cab", "aabb" and "baab".

The question is how to check if two strings are broth开发者_运维问答er string(fast)?

---

Sort them then compare, or keep a count of each character in a map of some sort then compare counts at the end.

---

Just count how many times each character is present in the string. And them compare the counts for the two strings you have.

If the strings are always ASCII or some 8-bit encoding, simple array is good enough for the counts.

If they can contain Unicode characters, use a hash map.

---

The fastest algorithm in this case has a complexity of O(n) where n is the length of the longest string.

Infact in O(n) you can create an array (one for each string) where the characters are stored. Besides, you need another O(n) time to do the test.

---

What about have an array of all characters and to count the number of a's b's etc' than compare the two array's

---

Let me show my variant. Each char has its int ASCII value. So I think, you may multiply all chars for both strings and compare two products. For example:

private static boolean compareForBrother(String s1, String s2) {
    long lProduct= 1L;
    for (byte b : s1.getBytes()) {
        lProduct *= b;
    }

    long lProduct2= 1L;
    for (byte b : s2.getBytes()) {
        lProduct2 *= b;
    }

    return (lProduct2 == lProduct);
}

---

Compare the set of characters in each string.

In python, something like:

if set(stringA) == set(stringB):
    print("%s and %s are brother strings" % (stringA, stringB))

---

Prepare a histogram of character frequencies; this is fwiw exactly the same process as a radix sort. Then compare the histograms.