Hi, not able to wrap my head around why 2nd code snippet has better performance than the 1st.
This is C# code with reference to the problem.
https://leetcode.com/problems/find-all-anagrams-in-a-string/
Pasting the entire code below
if(end - start + 1 == p.Length)
{
if(count == 0)
output.Add(start);
if(map[s[start] - 'a']++ >= 0)
count++;
start++;
} if(count == 0)
{
output.Add(start);
}
if(end - start + 1 == p.Length && map[s[start++] - 'a']++ >= 0)
count++;Complete code:
public IList<int> FindAnagrams(string s, string p) {
List<int> output = new List<int>();
if(s == null || s.Length == 0)
return output;
int[] map = new int[26];
foreach(char c in p.ToCharArray())
{
map[c - 'a']++;
}
int count = p.Length;
int start = 0;
int end;
for(end = 0; end < s.Length; end++)
{
if(map[s[end] - 'a']-- > 0)
{
count--;
}
if(count == 0)
{
output.Add(start);
}
if(end - start + 1 == p.Length && map[s[start++] - 'a']++ >= 0)
count++;
}
return output;
}
}