242

We can solve it with a dictionary,

public class Solution {
    public bool IsAnagram(string s, string t) {
        if (s.Length != t.Length)
	        return false;
	        
		var dict = new Dictionary<char, int>();
		
		foreach (char c in s)
		{
			if (dict.ContainsKey(c))
				dict[c]++;
			else 
				dict[c] = 1;
		}
		
		foreach (char c in t)
		{
			if (!dict.ContainsKey(c))
				return false;
				
			dict[c]--;
			
			if (dict[c] < 0)
				return false;
		}
		
		return true;
    }
}

Earlier I tried using dict.Remove and checking dict.count is zero at the end, but this logic of decrementing and checking less than zero is better. And early return on not finding key is good.

---

And even with an array, since it is only lowercase English letters,

public class Solution {
    public bool IsAnagram(string s, string t) {
        if (s.Length != t.Length)
            return false;
 
        int[] count = new int[26];
 
        foreach (char c in s)
            count[c - 'a']++;
 
        foreach (char c in t) {
            count[c - 'a']--;
            if (count[c - 'a'] < 0)
                return false;
        }
 
        return true;
    }
}

---

Both these solutions are $O(n)$ time, and for space, array solution is $O(1)$ and dictionary one, is $O(k)$, where k is the number of distinct characters. Like, total characters in Unicode etc.