tygarian

find all anagrams in a string leetcode

Feb 2nd, 2022
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.45 KB | None | 0 0
  1. class Solution {
  2. public:
  3. // Time Complexity:- O(max(N,26))
  4. // Space Complexity:- O(26)
  5. vector<int> findAnagrams(string s, string p) {
  6. int n = s.length(),m = p.length();
  7.  
  8. // not possible for this case
  9. if(m>n){
  10. return {};
  11. }
  12.  
  13. // if p is an anagram of some substring of s, then their frequency must be same
  14. vector<int> demand_frequency(26),substring_frequency(26),ans;
  15. for(auto& c:p){
  16. demand_frequency[c-'a']++;
  17. }
  18. for(int i=0;i<m;i++){
  19. substring_frequency[s[i]-'a']++;
  20. }
  21.  
  22. // deviation = number of characters whose frequency aren't equal to demand frequency
  23. int deviation = 0;
  24. for(int i=0;i<26;i++){
  25. deviation += (demand_frequency[i]!=substring_frequency[i]);
  26. }
  27.  
  28. // fill answer for first substring of m length
  29. if(deviation==0){
  30. ans.push_back(0);
  31. }
  32.  
  33. for(int i=m;i<n;i++){
  34. int j = s[i] - 'a'; // add the current character to current frequency array
  35. substring_frequency[j]++;
  36. // if their frequency matches now, it means previously their frequency didn't match, hence we do deviation-- in this case
  37. if(substring_frequency[j]==demand_frequency[j]){
  38. deviation--;
  39. }
  40. // if current frequency of character exceeds the demand frequency of character by exactly 1, means previously they have same frequency
  41. else if(substring_frequency[j]-demand_frequency[j]==1){
  42. deviation++;
  43. }
  44.  
  45. j = s[i-m] - 'a';
  46. substring_frequency[j]--;
  47. // if their frequency matches now, it means previously their frequency didn't match, hence we do deviation-- in this case
  48. if(substring_frequency[j]==demand_frequency[j]){
  49. deviation--;
  50. }
  51. // if demand frequency of character exceeds the current frequency of character by exactly 1, means previously they have same frequency
  52. else if(demand_frequency[j]-substring_frequency[j]==1){
  53. deviation++;
  54. }
  55.  
  56. // if deviation is 0, means all characters have their desired frequency
  57. if(deviation==0){
  58. ans.push_back(i-m+1);
  59. }
  60. }
  61.  
  62. return ans;
  63. }
  64. };
Add Comment
Please, Sign In to add comment