Welcome to Subscribe On Youtube
  • import java.util.ArrayList;
    import java.util.List;
    
    /**
    
     Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
    
     Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
    
     The order of output does not matter.
    
     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".
    
     */
    
    public class Find_All_Anagrams_in_a_String {
    
        public class Solution {
            public List<Integer> findAnagrams(String s, String p) {
                List<Integer> res = new ArrayList<>();
                if (p == null || s == null || s.length() < p.length()) return res;
                int m = s.length(), n = p.length();
                for (int i = 0; i < m-n+1; i++) {
                    String cur = s.substring(i, i+n);
                    if (helper(cur, p)) {
                        res.add(i);
                    }
                }
                return res;
            }
            public boolean helper(String a, String b) {
    
                if (a == null || b == null || a.length() != b.length()) {
                    return false;
                }
    
                int[] dict = new int[26];
    
                // 2*logN is better than sorting 2*NlogN
                for (int i = 0; i < a.length(); i++) {
                    char ch = a.charAt(i);
                    dict[ch-'a']++;
                }
    
                for (int i = 0; i < b.length(); i++) {
                    char ch = b.charAt(i);
                    dict[ch-'a']--;
                    if (dict[ch-'a'] < 0) return false;
                }
    
                return true;
            }
        }
    }
    
    ############
    
    class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            int[] counter = new int[26];
            for (char c : p.toCharArray()) {
                ++counter[c - 'a'];
            }
            List<Integer> ans = new ArrayList<>();
            int left = 0, right = 0;
            int[] t = new int[26];
            while (right < s.length()) {
                int i = s.charAt(right) - 'a';
                ++t[i];
                while (t[i] > counter[i]) {
                    --t[s.charAt(left) - 'a'];
                    ++left;
                }
                if (right - left + 1 == p.length()) {
                    ans.add(left);
                }
                ++right;
            }
            return ans;
        }
    }
    
  • class Solution:
        def findAnagrams(self, s: str, p: str) -> List[int]:
            counter = Counter(p)
            ans = []
            left = right = 0
            t = Counter()
            while right < len(s):
                t[s[right]] += 1
                while t[s[right]] > counter[s[right]]:
                    t[s[left]] -= 1
                    left += 1
                if right - left + 1 == len(p):
                    ans.append(left)
                right += 1
            return ans
    
    ############
    
    from collections import Counter
    
    
    class Solution(object):
      def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        sCount = Counter(s[:len(p) - 1])
        pCount = Counter(p)
        ans = []
    
        for i in range(len(p) - 1, len(s)):
          sCount[s[i]] += 1
          if sCount == pCount:
            ans.append(i - len(p) + 1)
          sCount[s[i - len(p) + 1]] -= 1
          if sCount[s[i - len(p) + 1]] == 0:
            del sCount[s[i - len(p) + 1]]
        return ans
    
    
  • class Solution {
    public:
        vector<int> findAnagrams(string s, string p) {
            vector<int> counter(26);
            for (char c : p) ++counter[c - 'a'];
            vector<int> ans;
            int left = 0, right = 0;
            vector<int> t(26);
            while (right < s.size()) {
                int i = s[right] - 'a';
                ++t[i];
                while (t[i] > counter[i]) {
                    --t[s[left] - 'a'];
                    ++left;
                }
                if (right - left + 1 == p.size()) ans.push_back(left);
                ++right;
            }
            return ans;
        }
    };
    
  • func findAnagrams(s string, p string) []int {
    	counter := make([]int, 26)
    	for _, c := range p {
    		counter[c-'a']++
    	}
    	var ans []int
    	left, right := 0, 0
    	t := make([]int, 26)
    	for right < len(s) {
    		i := s[right] - 'a'
    		t[i]++
    		for t[i] > counter[i] {
    			t[s[left]-'a']--
    			left++
    		}
    		if right-left+1 == len(p) {
    			ans = append(ans, left)
    		}
    		right++
    	}
    	return ans
    }
    
  • function findAnagrams(s: string, p: string): number[] {
        let n = s.length,
            m = p.length;
        let cnt = new Array(26).fill(0);
        let ans = [];
        for (let i = 0; i < m; i++) {
            cnt[p.charCodeAt(i) - 97]--;
            cnt[s.charCodeAt(i) - 97]++;
        }
        if (cnt.every(v => v == 0)) {
            ans.push(0);
        }
        for (let i = m; i < n; i++) {
            cnt[s.charCodeAt(i) - 97]++;
            cnt[s.charCodeAt(i - m) - 97]--;
            if (cnt.every(v => v == 0)) {
                ans.push(i - m + 1);
            }
        }
        return ans;
    }
    
    
  • impl Solution {
        pub fn find_anagrams(s: String, p: String) -> Vec<i32> {
            let (s, p) = (s.as_bytes(), p.as_bytes());
            let (m, n) = (s.len(), p.len());
            let mut res = vec![];
            if n > m {
                return res;
            }
    
            let mut counter = [0; 26];
            for i in 0..n {
                counter[(p[i] - b'a') as usize] += 1;
                counter[(s[i] - b'a') as usize] -= 1;
            }
            for i in n..m {
                if counter.iter().all(|&v| v == 0) {
                    res.push((i - n) as i32);
                }
                counter[(s[i] - b'a') as usize] -= 1;
                counter[(s[i - n] - b'a') as usize] += 1;
            }
            if counter.iter().all(|&v| v == 0) {
                res.push((m - n) as i32);
            }
            res
        }
    }
    
    
  • public class Solution {
        public IList<int> FindAnagrams(string s, string p) {
            int m = s.Length, n = p.Length;
            IList<int> ans = new List<int>();
            if (m < n) {
                return ans;
            }
            int[] cnt1 = new int[26];
            int[] cnt2 = new int[26];
            for (int i = 0; i < n; ++i) {
                ++cnt1[p[i] - 'a'];
            }
            for (int i = 0, j = 0; i < m; ++i) {
                int k = s[i] - 'a';
                ++cnt2[k];
                while (cnt2[k] > cnt1[k]) {
                    --cnt2[s[j++] - 'a'];
                }
                if (i - j + 1 == n) {
                    ans.Add(j);
                }
            }
            return ans;
        }
    }
    
  • class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            List<Integer> indices = new ArrayList<Integer>();
            if (s == null || p == null || s.length() < p.length())
                return indices;
            int sLength = s.length();
            int pLength = p.length();
            int[] sCount = new int[26];
            int[] pCount = new int[26];
            for (int i = 0; i < pLength; i++) {
                sCount[s.charAt(i) - 'a']++;
                pCount[p.charAt(i) - 'a']++;
            }
            if (match(sCount, pCount))
                indices.add(0);
            for (int i = pLength; i < sLength; i++) {
                char prevC = s.charAt(i - pLength), curC = s.charAt(i);
                sCount[prevC - 'a']--;
                sCount[curC - 'a']++;
                if (match(sCount, pCount))
                    indices.add(i - pLength + 1);
            }
            return indices;
        }
    
        public boolean match(int[] sCount, int[] pCount) {
            for (int i = 0; i < 26; i++) {
                if (sCount[i] != pCount[i])
                    return false;
            }
            return true;
        }
    }
    
    ############
    
    class Solution {
        public List<Integer> findAnagrams(String s, String p) {
            int[] counter = new int[26];
            for (char c : p.toCharArray()) {
                ++counter[c - 'a'];
            }
            List<Integer> ans = new ArrayList<>();
            int left = 0, right = 0;
            int[] t = new int[26];
            while (right < s.length()) {
                int i = s.charAt(right) - 'a';
                ++t[i];
                while (t[i] > counter[i]) {
                    --t[s.charAt(left) - 'a'];
                    ++left;
                }
                if (right - left + 1 == p.length()) {
                    ans.add(left);
                }
                ++right;
            }
            return ans;
        }
    }
    
  • class Solution:
        def findAnagrams(self, s: str, p: str) -> List[int]:
            counter = Counter(p)
            ans = []
            left = right = 0
            t = Counter()
            while right < len(s):
                t[s[right]] += 1
                while t[s[right]] > counter[s[right]]:
                    t[s[left]] -= 1
                    left += 1
                if right - left + 1 == len(p):
                    ans.append(left)
                right += 1
            return ans
    
    ############
    
    from collections import Counter
    
    
    class Solution(object):
      def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        sCount = Counter(s[:len(p) - 1])
        pCount = Counter(p)
        ans = []
    
        for i in range(len(p) - 1, len(s)):
          sCount[s[i]] += 1
          if sCount == pCount:
            ans.append(i - len(p) + 1)
          sCount[s[i - len(p) + 1]] -= 1
          if sCount[s[i - len(p) + 1]] == 0:
            del sCount[s[i - len(p) + 1]]
        return ans
    
    
  • class Solution {
    public:
        vector<int> findAnagrams(string s, string p) {
            vector<int> counter(26);
            for (char c : p) ++counter[c - 'a'];
            vector<int> ans;
            int left = 0, right = 0;
            vector<int> t(26);
            while (right < s.size()) {
                int i = s[right] - 'a';
                ++t[i];
                while (t[i] > counter[i]) {
                    --t[s[left] - 'a'];
                    ++left;
                }
                if (right - left + 1 == p.size()) ans.push_back(left);
                ++right;
            }
            return ans;
        }
    };
    
  • func findAnagrams(s string, p string) []int {
    	counter := make([]int, 26)
    	for _, c := range p {
    		counter[c-'a']++
    	}
    	var ans []int
    	left, right := 0, 0
    	t := make([]int, 26)
    	for right < len(s) {
    		i := s[right] - 'a'
    		t[i]++
    		for t[i] > counter[i] {
    			t[s[left]-'a']--
    			left++
    		}
    		if right-left+1 == len(p) {
    			ans = append(ans, left)
    		}
    		right++
    	}
    	return ans
    }
    
  • function findAnagrams(s: string, p: string): number[] {
        let n = s.length,
            m = p.length;
        let cnt = new Array(26).fill(0);
        let ans = [];
        for (let i = 0; i < m; i++) {
            cnt[p.charCodeAt(i) - 97]--;
            cnt[s.charCodeAt(i) - 97]++;
        }
        if (cnt.every(v => v == 0)) {
            ans.push(0);
        }
        for (let i = m; i < n; i++) {
            cnt[s.charCodeAt(i) - 97]++;
            cnt[s.charCodeAt(i - m) - 97]--;
            if (cnt.every(v => v == 0)) {
                ans.push(i - m + 1);
            }
        }
        return ans;
    }
    
    
  • impl Solution {
        pub fn find_anagrams(s: String, p: String) -> Vec<i32> {
            let (s, p) = (s.as_bytes(), p.as_bytes());
            let (m, n) = (s.len(), p.len());
            let mut res = vec![];
            if n > m {
                return res;
            }
    
            let mut counter = [0; 26];
            for i in 0..n {
                counter[(p[i] - b'a') as usize] += 1;
                counter[(s[i] - b'a') as usize] -= 1;
            }
            for i in n..m {
                if counter.iter().all(|&v| v == 0) {
                    res.push((i - n) as i32);
                }
                counter[(s[i] - b'a') as usize] -= 1;
                counter[(s[i - n] - b'a') as usize] += 1;
            }
            if counter.iter().all(|&v| v == 0) {
                res.push((m - n) as i32);
            }
            res
        }
    }
    
    
  • public class Solution {
        public IList<int> FindAnagrams(string s, string p) {
            int m = s.Length, n = p.Length;
            IList<int> ans = new List<int>();
            if (m < n) {
                return ans;
            }
            int[] cnt1 = new int[26];
            int[] cnt2 = new int[26];
            for (int i = 0; i < n; ++i) {
                ++cnt1[p[i] - 'a'];
            }
            for (int i = 0, j = 0; i < m; ++i) {
                int k = s[i] - 'a';
                ++cnt2[k];
                while (cnt2[k] > cnt1[k]) {
                    --cnt2[s[j++] - 'a'];
                }
                if (i - j + 1 == n) {
                    ans.Add(j);
                }
            }
            return ans;
        }
    }
    

All Problems

All Solutions