Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Alternate C++ solution -- 2 maps

Roberto Pantoja

Jun 15, 2023

Use two maps - one holds char freq. of pattern, the other holds char freq. of current window.

static bool findPermutation(const string &str, const string &pattern) { unordered_map<char, int> pattern_map; unordered_map<char, int> string_map; int K = pattern.size(), start = 0; for(char c : pattern) pattern_map[c]++; for(int end = 0; end < str.size(); end++){ string_map[str.at(end)]++; if(end > K - 1){ string_map[str.at(start)]--; if(string_map[str.at(start)] <= 0) string_map.erase(str.at(start)); start++; } if(string_map == pattern_map) return true; } return false; }

If at any point both maps are the same, we have found the permutation.

The added map adds some space complexity, but I find this solution much easier to follow.

0

0

Comments
Comments

On this page