O(n) solution regardless of the alphabet used.


  • 0
    T

    This solution is O(n) and is independent of the character set used. If we used a language with 1000000 letters it would run in O(n). The space is O(#characters in the language), however. Other solutions are comparing frequency vectors which yields O(n*k) complexity for a character set of size k. The idea is simply to maintain a matching variable that indicates the number of matches in frequencies we've seen between the string and the pattern. Each shifting of the window requires O(1) operations to maintain this variable.

    class Solution {
    public:
        vector<int> findAnagrams(string s, string p) {
            int matching = 0;
            vector<int> freq_s(26);
            vector<int> freq_p(26);
            
            for(auto str : p) {
                if(freq_p[str-'a'] == 0) matching++;
                freq_p[str - 'a']++;
            }
            
            vector<int> indexes;
            
            matching = 26 - matching; //number of chars that match initially since they have 0 occurrences in p.
            int i = 0;
            for(; i < p.length(); i++) {
                if(freq_s[s[i] - 'a'] == freq_p[s[i] - 'a']) {
                    matching--;
                }
                freq_s[s[i] - 'a']++;
                if(freq_s[s[i] - 'a'] == freq_p[s[i] - 'a']) {
                    matching++;
                }
            }
            
            cout << matching << endl;
            
            if(matching == 26) {
                indexes.push_back(i - p.length());
            }
            
            for(; i < s.length(); i++) {
                //lost i - p.length():
                int index = s[i-p.length()] - 'a';
                if(freq_p[index] == freq_s[index]) {
                    matching--;
                }
                freq_s[index]--;
                if(freq_p[index] == freq_s[index]) {
                    matching++;
                }
                
                index = s[i] - 'a';
                if(freq_p[index] == freq_s[index]) {
                    matching--;
                }
                freq_s[index]++;
                if(freq_p[index] == freq_s[index]) {
                    matching++;
                }
                
                if(matching == 26) {
                    indexes.push_back(i - p.length()+1);
                }
            }
            
            return indexes;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.