Chapter 1 - Problem 2.2 - Check Permutation
Problem
Given a smaller string s1 and a bigger string s2, design an algorithm to find all permutations of the shorter string within the longer one. Returnย an array of all the start indices of ย s1's anagrams in s2.
Solution
The assumptions are the same of Problem 2.1 - Check Permutation.
Solution in C++ with array
This problem is similar to Problem 2.1 - Check Permutation, but here we have to find all the permutation occurences. To do that, we start sliding the windowย [0..len(s1)]ย overย s2. Every time a letter gets out of the window, we decrease the corresponding counter in the array and when a letter gets in the window, we increase it. Now we just have to compare s1 with the sliding window.
std::vector<int> checkPermutationstring s1, std::string s2 {
std::vector<int> answer;
int s1_size = s1.size();
int s2_size = s2.size();
if(s1_size > s2_size) return {};
std::array<int, 128> s1_charSet = {};
std::array<int, 128> s2_charSet = {};
//initialize s1 and s2 hash maps
for(int i = 0; i < s1_size; i++) {
s1_charSet.at(s1.at(i))++;
s2_charSet.at(s2.at(i))++;
}
//first check
if(s1_charSet == s2_charSet) answer.push_back(0);
//it's a sliding window, each iteration the window slides at right
for(int i = 0; (s1_size + i) < s2_size; i++) {
int right_index = (int)s2.at(s1_size + i); //character to add in hash map
int left_index = (int)s2.at(i); //character to delete in hash map
s2_charSet.at(right_index)++;
s2_charSet.at(left_index)--;
if(s1_charSet == s2_charSet) answer.push_back(i+1);
}
return answer;
}
- Time complexity:
(one pass over s1, one pass forยs2) - Space complexity:
( char_setwill always have 128 elements)