0

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 brother string(fast)?

wong2
  • 34,358
  • 48
  • 134
  • 179

7 Answers7

4

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

JRL
  • 76,767
  • 18
  • 98
  • 146
  • So which one is it? Sorting or counting? What are the differences between the two options? – svick Oct 08 '11 at 14:26
  • Counting is O(n), sorting depend on the method you use. – lostyzd Oct 08 '11 at 14:28
  • Counting is easy... make two 26-integer arrays, iterate through the strings and increment the respective counter for each character in the string. At the end, you XOR the counters together and they're brothers if everything is 0. –  Oct 10 '11 at 04:34
2

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.

svick
  • 236,525
  • 50
  • 385
  • 514
1

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.

Mob
  • 10,958
  • 6
  • 41
  • 58
Aurelio De Rosa
  • 21,856
  • 8
  • 48
  • 71
  • The strings will have to be of the same length, if I understand what he describes aright. – Chris Morgan Oct 08 '11 at 14:27
  • I have no idea what are you talking about. – svick Oct 08 '11 at 14:27
  • @AurelioDeRosa, I know what big O notation means. But I don't know how does your answer actually relate to the question. You talk about creating some array and then doing some test. But it's not clear what array do you want to create and what test do you want to perform. – svick Oct 08 '11 at 14:39
  • I thought I'm talking to professional programmes and so it is clear that "test" in this case means compare (char by char) and that the array will contains the chars of the string. – Aurelio De Rosa Oct 08 '11 at 14:45
  • @AurelioDeRosa, then I don't understand what does that have to do with the question. How will your solution find that `abc` and `cab` are brother strings? – svick Oct 08 '11 at 17:10
  • 1
    Have I to write the code? I don't want to do. I don't want to do the work for others. I gave my idea and my suggestion on how to proceed and that's all. – Aurelio De Rosa Oct 08 '11 at 17:36
0

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

Belgi
  • 14,542
  • 22
  • 58
  • 68
0

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);
}
Ilja Hämäläinen
  • 165
  • 2
  • 11
0

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))
Paddy3118
  • 4,704
  • 27
  • 38
0

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

phunctor
  • 599
  • 3
  • 9