LeetCode 438. Find All Anagrams in a String

https://leetcode.com/problems/find-all-anagrams-in-a-string/description/

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc". 

Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

---

• 字符串题。弄清楚Sliding Window algorithm之后简单。
• 首先对string p做hash。假设在string s上有一个window，如果匹配一个hash[i]，就对-- hash[i]的话，最终结果就是要找到一个window宽度为p.size()，同时所有hash[i]都为0，即所有字符都匹配。
• 基于这个思想，我们可以观察到
  • the sum of all hash[i] is always >=0;
  • count is the sum of all positive hash[i];
  • therefore, every hash[i] is zero if and only if count is 0.
• 有了这个原则后，我们可以用两个指针指向window的left和right，count初始为p.size()，实际上是sum(hash[i])。然后开始移动right来扩展window，如果匹配，则-- count，然后继续移动right去扩展window。同时-- hash[right]，即对当前window中的char的hash值进行修改。
• 如果window的宽度为p.size()，即right - left == p.size()，那么判断如果count == 0则代表所有hash[i]已经匹配了，也就是找到匹配的anagram了。然后把window向右移动，即++ left。同时如果原先s[left]是存在于p中的，即hash[left] >= 0，则++ count复原。同时原先left处的字符已经不在当前window里了，则++ hash[left]来复原。
• 算法里注意对right指针对应的char的操作都是--，对left指针的则是++。对right指针进行的修改，在left移出window时会都复原，这样可以保证每个window初始时值都是一样。
• Find All Anagrams in a String - LeetCode
  • https://leetcode.com/problems/find-all-anagrams-in-a-string/discuss/92015/ShortestConcise-JAVA-O(n)-Sliding-Window-Solution

//
//  main.cpp
//  LeetCode
//
//  Created by Hao on 2017/3/16.
//  Copyright © 2017年 Hao. All rights reserved.
//

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> vResult;
        
        // corner case
        if (s.empty() || p.empty() || s.size() < p.size()) return vResult;
        
        unordered_map<char, int>    hash;
        
        // hash chars in p
        for (auto ch : p)
            ++ hash[ch];
        
        // two points indicating the begin/end of the window
        // count actually means the sum of all positive hash[i], and the sum of all hash[i] is always >= 0
        int left = 0, right = 0, count = p.size();
        
        while (right < s.size()) {
            // move window's right point rightward, if the char exists in p, decrease the count
            if (hash[s.at(right)] > 0)
                -- count;
            
            -- hash[s.at(right)];
            
            ++ right;
            
            // if the window's width == p.size(), then we have to slide window rightward for a new window, move the left point rightward
            if (right - left == p.size()) {
                // count == 0 if and only if every hash[i] == 0, means we find the anagram
                if (0 == count)
                    vResult.push_back(left);
                
                // Only increase the count if the char exists in p
                if (hash[s.at(left)] >= 0)
                    ++ count;
                
                ++ hash[s.at(left)];
                
                ++ left;
            }
        }
        
        return vResult;
    }
};

int main(int argc, char* argv[])
{
    Solution    testSolution;
    
    vector<string> iVec = {"cbaebabacd", "abc", "abab", "ab"};
    vector<int>     result;
    
    /*
     0 6
     0 1 2
     */
    for (int i = 0; i < iVec.size() - 1; i += 2) {
        result = testSolution.findAnagrams(iVec[i], iVec[i + 1]);
        
        for (auto it : result)
            cout << it << " ";
        cout << endl;
    }
    
    return 0;
}