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
    }
}

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
    }
}

438 - Find All Anagrams in a String

All Problems

All Solutions

Welcome to Subscribe On Youtube

All Problems

All Solutions