title: Find all permutations of smaller string s in string b (JavaScript)
body: <p>I've been trying to find a O(n) solution to the following problem: Find the number of anagrams (permutations) of string s in string b, where s.length will always be smaller than b.length</p>
  
  <p>I read that the optimal solution involves keeping track of the frequencies of the characters in the smaller string and doing the same for the sliding window as it moves across the larger string, but I'm not sure how that implementation actually works. Right now my solution doesn't work (see comments) but even if it did, it would take O(s + sn) time. </p>
  
  <p>EDIT: Sample input: <code>('aba', 'abaab')</code>. Output: 3, because <code>'aba'</code> exists in b starting at index 0, and <code>'baa'</code> at 1, and <code>'aab'</code> at 2.</p>
  
  <pre><code>function anagramsInStr(s,b) {
  
      //O(s)
      let freq = s.split("").reduce((map, el) =&gt; {
          map[el] = (map[el] + 1) || 1;
          return map;
      }, {});
  
      let i = 0, j = s.length;
      // O(n)
      for (let char in b.split("")) {
          // O(s)
          if (b.length - char + 1 &gt; s.length) {
  
              let window = b.slice(i,j);
  
              let windowFreq = window.split("").reduce((map, el) =&gt; {
                  map[el] = (map[el] + 1) || 1;
                  return map;
              }, {});
              // Somewhere about here compare the frequencies of chars found in the window to the frequencies hash defined in the outer scope. 
              i++;
              j++;
  
          }
      }
  }
  </code></pre>