30 Substring with Concatenation of All Words

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.
For example,

given:
s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9]. (order does not matter).

Solution

class Solution {
public:
    bool isValid(unordered_map<string, int> dict, string s, int ns) {
        int n = s.size();
        for ( int i = 0; i <= n-1; i += ns ) {
            string word = s.substr(i, ns);
            if ( dict.find(word) == dict.end() ) return false;
            dict[word] -= 1;
            if ( dict[word] == 0 ) dict.erase(dict.find(word));
        }
        return true;
    }
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> res;
        int n = words.size();
        if ( n == 0 ) return res;
        int ns = words[0].size();
        int len = s.size();
        if ( len < n*ns ) return res;
        unordered_map<string, int> dict;
        for ( int i = 0; i <= n-1; i++ ) {
            string word = words[i];
            if ( dict.find(word) == dict.end() ) dict[word] = 1;
            else dict[word] += 1;
        }
        for ( int i = 0; i <= len - n*ns; i++ ) {
            if ( isValid(dict, s.substr(i, n*ns), ns) ) res.push_back(i);
        }
        return res;
    }
};

Notes
Similar to the "DNA sequence problem". Note the use of hashtable.