Leetcode discuss: 438. Find All Anagrams in a String

 Here is the link. 

TLE error - C# - First try - Reading skills

Dec. 29, 2020
Introduction
It is important to train myself to read very well. There is timeout issue if O(NlogN) sorting algorithm is applied to a string.

The string is given with the constaint "Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.". It can take O(N) time to determine if a string is anagram of another string. N is 20,100, NlgN will be around 80,000. This should be a warning number to avoid timeout.

The following code has TLE problem. This is my first try in my mock interview on premium version.

Time complexity:
O(N*M*logM), N is length of string s, M is length of P
The solution is not working, the time complexity should be O(N*M).

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>(); 
        
        if(sLength == pLength && s.CompareTo(p) == 0)
        {
            list.Add(0);
            return list; 
        }        
        
        var pArray = p.ToCharArray();
        Array.Sort(pArray);
        var sortedP = new string(pArray); 
        
        var found = new HashSet<string>(); 
        
        for(int i = 0; i < sLength && i + pLength <= sLength; i++)
        {
            var substring = s.Substring(i, pLength);
            var addToList = false; 
            if(found.Contains(substring))
            {
                addToList = true; 
            }
            else
            {                
                var array = substring.ToCharArray();                
                Array.Sort(array);
            
                var sorted = new string(array);
                if(sorted.CompareTo(sortedP) == 0)
                {
                    addToList = true;                    
                }
            }
            
            if(addToList)
            {
                 list.Add(i);
                 found.Add(substring); 
            }
        }
        
        return list; 
    }
}