438. Find All Anagrams in a String

Medium (Trung bình) C++ 🔗 Xem trên LeetCode

📋 Đề Bài

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

 

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s = "abab", p = "ab"
Output: [0,1,2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

 

Constraints:

  • 1 <= s.length, p.length <= 3 * 104
  • s and p consist of lowercase English letters.

🧠 Thuật Toán & Kỹ Thuật

String (Chuỗi)
⏱️ Thời gian O(n²)
💾 Không gian O(n)

💻 Lời Giải

C++ 0438-find-all-anagrams-in-a-string.cpp 
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> cntS(26, 0), cntP(26, 0);
        int n = s.size();
        int m = p.size();
        if (m > n) {
            return {};
        }
        for (int i = 0; i < m; ++i) {
            cntS[s[i] - 'a']++;
            cntP[p[i] - 'a']++;
        }
        vector<int> ans;
        if (cntS == cntP) {
            ans.push_back(0);
        }
        for (int i = m; i < n; ++i) {
            cntS[s[i] - 'a']++;
            cntS[s[i - m] - 'a']--;
            if (cntS == cntP) {
                ans.push_back(i - m + 1);
            }
        }
        return ans;
    }
};