Anagram Consecutive LeetCode (Consecutive Anagram)

Given two words, determine if the first word, or any anagram of it, appears  in consecutive characters of the second word. For instance, tea appears as an anagram in the last three letters of slate, but let does not appear as an anagram in actor even though all the letters of let appear in slate. Return the anagram of the first word that has appeared in the second word. 

Example 1:

• Input: tea slate
• Sample Output: ate  

Example 2:

• Input: let slate
• Sample Output: NONE

This problem is well discussed in several forums including Page1, Page2, Page3 A collection of hundreds of interview questions and solutions are available in our blog at Interview Question

Solution 1: 

• use two nested loops and check for the whole window in the word2 to see if there is a match. Complexity: O(n^2)

Solution 2:

1. If first word is longer than the second one then there is no solution
2. If the first word is not longer than the second one do the following: 
1. keep track of the count of the characters in the first word 
2. start scanning the second word for the window equal to the length of the first word 
3. if the count of the every chars in the window is equal to the count of the chars in the first word then we found the match 
4. if not found in (c) advance the window by one character 
3. repeat (2) till a match is found or there is no more window left

 Complexity: O(n)

Solution