Is this a good way to check for an anagram if sorting is not allowed?

Question

So I decided to lookup some algorithms, and one of the ones I found was.. "Check if the string is an anagram" and without using Google for more than checking what an anagram is, I decided to write some code.

What the code is doing is that it takes two strings.

car and arc for instance, and then it takes the first character from the first string car (c) and compares it to each character in the 2nd string. If it finds it, it removes both the occurrences at each corresponding index.

Once it finishes the outer loop it checks if the two strings are the same, which if it was an anagram, both strings would equal "". And if they are, that means we've successfully found an anagram.

This feels like a super un-optimized version of a very simple problem. I later started Googling for other peoples solution and I quickly noticed that people would just check if they're the same when sorted, which makes a lot of sense. I feel very stupid for not have picked that up while writing the code, and I would of done the same thing if I knew that sorting was an option.

At least I know until next time so it wasn't for nothing. I just feel very silly.

Could someone look at my version and see what's good / bad about it, what could I have done to optimize it without using a sorting algorithm. If it even works 100% of the time and what the time complexity is compared to if you were to sort it for instance.

bool IsAnagram(string s1, string s2)
{
    if (s1.Length != s2.Length)
        return false;

    for (int x = 0; x < s1.Length; x++)
    {
        var tempChar = s1[x];
        for (int y = 0; y <= s2.Length - 1; y++)
        {
            if (s2[y] == tempChar)
            {
                s1 = s1.Remove(x, 1);
                s2 = s2.Remove(y, 1);
            }
        }
    }

    if (s1 == s2)
        return true;
    return false;
}

Answer 1

I feel very stupid for not have picked that up while writing the code, and I would of done the same thing if I knew that sorting was an option.

Your way of handling the problem, from trying to do it yourself and test it, and then look on how others solve it, is the right way of coding, and not the other way around. This is how you will harvest your skills. Just keep in mind that all other solutions are just a one way of solving the same problem, as same as yours. Other solutions will give some new techniques that might be applicable to other problems as well.

As for anagramy, re-ordering the characters would add additional operation cost to the solution, as well as using Remove. What you want to think of is to check the strings as is, without trying to manipulate them. This would give you the fastest solution possible.

For instance, we could use a Boolean array to track the characters, which would tell if the character has been visited or not. This would ensure that a character would be checked once, and would not need to do any modifications to the source.

Example :

private bool IsAnagram(string source, string target)
{
    if (source == null || target == null) return false;

    if (source.Length != target.Length) return false;

    // characters tracker 
    // true if matched, otherwise false
    BitArray matches = new BitArray(target.Length);

    bool isMatched;

    for (int x = 0; x < source.Length; x++)
    {
        var tempChar = source[x];

        isMatched = false;

        for (int y = 0; y < target.Length; y++)
        {
            // if this character is already matched, skip it.
            if (matches[y]) continue;

            if (target[y] == tempChar)
            {
                matches[y] = isMatched = true;
                break;
            }
        }

        // if no matches
        if (!isMatched) return false;
    }

    return true;
}

What we did here is created a BitArray with same size as the target string, each element in the array corresponds to a character in the target string. if the matches[y] is true, then it means that his character has been already checked, and we need to skip it. If a match has been found, then we set true to the BitArray along with isMatched flag, otherwise the isMatched will be false, which indicates that there is no match for the given character.

the isMatched flag has been used as shortcut indication, without it, we will need to use another loop on BitArray to check if all are true. (or simply return false if there is any false value).

Answer 2

This function sometimes throws an exception due to the improper repeated s1.Remove(x, 1) which eventually tries to remove a character that doesn't exist, that's definitely a bad thing. For every char tempChar in s1, some char is removed from s1 however many times tempChar occurs in s2, but that may remove the wrong character from s1, including characters that don't exist because the index is beyond the end of the string.

For example: s1 = "aaab", s2 = "abbb", after a couple of iterations, the offending Remove will attempt to remove a character from s1 that doesn't exist.

So let's say we fix that by ensuring only one character is removed each time, for example by putting a break after the two removes.

Now it doesn't throw exceptions anymore, but it's still wrong, because now the outer loop sometimes skips a character: a character was removed in the inner loop which decreases the indexes of the characters that came after it, but x++ still happens and it can take the index right past the character that was next in line.

That could be fixed by adding x -= 1; after the two removes, but before the break. Personally I don't like that solution though. IMO a rule of thumb should be: do not modify the loop index in the body of a for loop, only in the for statement itself. There may be some exceptions to that, but let's not make too many of them..

Another problem with the whole approach is that it is a quadratic time algorithm. Maybe it used to be cubic before the break, it's a bit confusing to reason about all the constantly changing sizes though, but IMO not really worth going too deep into the weeds on the incorrect version of the algorithm. The corrected version is still quadratic time, which is bad enough. The version with sorting reaches either O(n log n) or even O(n) (taking n as the sum of the lengths of the strings) depending on what kind of sorting is used (since we're sorting characters, a linear time sorting algorithm could be used). The alternative approach that builds a histogram for each string and then compared the histograms, would also take only linear time, and it would be simple to implement, I would rate that as simpler than the current implementation.

Miscellaneous notes

y <= s2.Length - 1

This is an unusual way to write y < s2.Length. It's not wrong, but I had to think about it for longer than I would have had to do if the usual pattern had been used.

if (s1 == s2)
    return true;
return false;

Could be written as return s1 == s2;