C# - O(n) - Simple sliding window solution


  • 0
    K
    public IList<int> FindAnagrams(string s, string p)
            {
                IList<int> list = new List<int>();
                if (string.IsNullOrWhiteSpace(s) || s.Length < p.Length)
                    return list;
                int sum = 0;
                int[] pArray = new int[26];
                foreach (char c in p)
                {
                    sum = sum + (c - 'a');
                    ++pArray[c - 'a'];
                }
                int sum1 = 0;
                int startIndex = 0;
    
                for (int endIndex = 0; endIndex < s.Length; endIndex++)
                {
                    // If no character is seen, reset all
                    if (pArray[s[endIndex] - 'a'] == 0)
                    {
                        sum1 = 0;
                        startIndex = endIndex + 1;
                        continue;
                    }
                     // If one is see, add the integer sum of that character
                    sum1 += s[endIndex] - 'a';
    
                    if (endIndex - startIndex + 1 == p.Length)
                    {
                        // Comparing the sums helps to make sure all the characters in the string "p" are included
                        if(sum1 == sum) list.Add(startIndex);
                        
                        // Subtract char at the start index because the window slides to right by one character discarding the already added one  
                        sum1 -= s[startIndex++] - 'a';
                    }
                }
    
                return list;
            }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.