Leetcode discuss: 438. Find All Anagrams in a String

 Here is the link. 

Second practice - C# - Linear time - Counting sort

Dec. 29, 2020
Introduction
My first practice ran into time out problem since the sorting is applied. I read the problem statement again and then decide to use counting sort with linear time, the problem is solved.

Edge case
I ran into the wrong answer, so that I figured out that extra checking is needed in the function isAnagram.

if(count[item - 'a'] < 1 )
{
    return false; 
}

20 days break

I just took 20 days break after Dec. 8. It is surprising to learn from my two mistakes I had in my practice.

public class Solution {
    public IList<int> FindAnagrams(string s, string p) {
        if(s == null || p == null || s.Length == 0 || p.Length == 0 || s.Length < p.Length)
            return new List<int>(); 
        
        var sLength = s.Length; 
        var pLength = p.Length; 
        
        var list = new List<int>();                                   
        
        for(int i = 0; i < sLength && i + pLength <= sLength; i++)
        {
            var substring = s.Substring(i, pLength);
                        
            if(isAnagram(substring, p))
            {
                list.Add(i);
            }
        }
        
        return list; 
    }
    
    private bool isAnagram(string s, string t)
    {
        var count = new int[26];
        foreach(var item in s)
        {
            count[item - 'a']++;
        }
        
        foreach(var item in t)
        {
            if(count[item - 'a'] < 1 )
            {
                return false; 
            }
            
            count[item - 'a']--;
        }
        
        return count.Sum() == 0;         
    }
}