Find All Anagrams In A String

                                            
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        
        if (s == null || s.length() == 0 || p == null || p.length() == 0) {
            return result;
        }
        
        int[] target = new int[26], window = new int[26];
        for (char c : p.toCharArray()) {
            target[c - 'a']++;
        }
        
        int left = 0, right = 0, count = p.length();
        while (right < s.length()) {
            if (target[s.charAt(right) - 'a'] > 0) {
                window[s.charAt(right) - 'a']++;
                if (window[s.charAt(right) - 'a'] <= target[s.charAt(right) - 'a']) {
                    count--;
                }
            }
            
            if (right - left + 1 > p.length()) {
                if (window[s.charAt(left) - 'a'] > 0) {
                    if (window[s.charAt(left) - 'a'] <= target[s.charAt(left) - 'a']) {
                        count++;
                    }
                    window[s.charAt(left) - 'a']--;
                }
                left++;
            }
            
            if (count == 0) {
                result.add(left);
            }
            
            right++;
        }
        
        return result;
    }
}

                                            
class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        if not s or not p or len(s) < len(p):
            return []

        result = []
        p_count = collections.Counter(p)
        s_count = collections.Counter(s[:len(p)-1])

        for i in range(len(p)-1, len(s)):
            s_count[s[i]] += 1
            if s_count == p_count:
                result.append(i - len(p) + 1)
            s_count[s[i - len(p) + 1]] -= 1
            if s_count[s[i - len(p) + 1]] == 0:
                del s_count[s[i - len(p) + 1]]

        return result

                                            
public class Solution {
    public IList<int> FindAnagrams(string s, string p) {
        List<int> result = new List<int>();
        
        if (s == null || s.Length == 0 || p == null || p.Length == 0) {
            return result;
        }
        
        int[] charCount = new int[26];
        foreach (char c in p) {
            charCount[c - 'a']++;
        }
        
        int left = 0, right = 0, count = p.Length;
        
        while (right < s.Length) {
            if (charCount[s[right] - 'a'] > 0) {
                count--;
            }
            charCount[s[right] - 'a']--;
            right++;
            
            if (count == 0) {
                result.Add(left);
            }
            
            if (right - left == p.Length) {
                if (charCount[s[left] - 'a'] >= 0) {
                    count++;
                }
                charCount[s[left] - 'a']++;
                left++;
            }
        }
        
        return result;
    }
}

                                            
/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
const findAnagrams = (s, p) => {
    const result = [];
    const map = new Map();
    for (let char of p) {
        map.set(char, map.get(char) + 1 || 1);
    }
    let left = 0, right = 0, count = p.length;
    
    while (right < s.length) {
        if (map.has(s[right]) && map.get(s[right]) > 0) {
            map.set(s[right], map.get(s[right]) - 1);
            count--;
            right++;
        } else if (map.has(s[left])) {
            map.set(s[left], map.get(s[left]) + 1);
            count++;
            left++;
        } else {
            right++;
            left = right;
            count = p.length;
        }
        
        if (count === 0) {
            result.push(left);
            map.set(s[left], map.get(s[left]) + 1);
            count++;
            left++;
        }
    }
    
    return result;
};

                                            
function findAnagrams(s: string, p: string): number[] {
    const result: number[] = [];
    if (s.length < p.length) {
        return result;
    }

    const charCountP: number[] = Array(26).fill(0);
    const charCountS: number[] = Array(26).fill(0);
    const aCharCode = "a".charCodeAt(0);

    for (let i = 0; i < p.length; i++) {
        charCountP[p.charCodeAt(i) - aCharCode]++;
        charCountS[s.charCodeAt(i) - aCharCode]++;
    }

    for (let i = 0; i <= s.length - p.length; i++) {
        if (charCountP.join("") === charCountS.join("")) {
            result.push(i);
        }

        if (i < s.length - p.length) {
            const startPos = s.charCodeAt(i) - aCharCode;
            const endPos = s.charCodeAt(i + p.length) - aCharCode;
            charCountS[startPos]--;
            charCountS[endPos]++;
        }
    }

    return result;
};

                                            
class Solution {
    func findAnagrams(_ s: String, _ p: String) -> [Int] {
        var result = [Int]()
        let pArr = Array(p)
        var pMap = [Character: Int]()
        
        for char in pArr {
            pMap[char, default: 0] += 1
        }
        
        let sArr = Array(s)
        var sMap = [Character: Int]()
        
        for i in 0..<sArr.count {
            sMap[sArr[i], default: 0] += 1
            if i >= pArr.count {
                let start = i - pArr.count
                if let count = sMap[sArr[start]] {
                    if count == 1 {
                        sMap.removeValue(forKey: sArr[start])
                    } else {
                        sMap[sArr[start]] = count - 1
                    }
                }
            }
            
            if i >= pArr.count - 1 && sMap == pMap {
                result.append(i - pArr.count + 1)
            }
        }
        
        return result
    }
}

                                            
func findAnagrams(s string, p string) []int {
    var result []int
    if len(s) == 0 || len(p) == 0 {
        return result
    }

    pCount := make(map[byte]int)
    for i := 0; i < len(p); i++ {
        pCount[p[i]]++
    }

    left, right := 0, 0
    remaining := len(p)

    for right < len(s) {
        if pCount[s[right]] > 0 {
            remaining--
        }
        pCount[s[right]]--
        right++

        if remaining == 0 {
            result = append(result, left)
        }

        if right-left == len(p) {
            if pCount[s[left]] >= 0 {
                remaining++
            }
            pCount[s[left]]++
            left++
        }
    }

    return result
}

                                            
# @param {String} s
# @param {String} p
# @return {Integer[]}
def find_anagrams(s, p)
    result = []
    return result if s.length < p.length
    
    p_freq = Array.new(26, 0)
    s_freq = Array.new(26, 0)
    
    p.each_char { |char| p_freq[char.ord - 'a'.ord] += 1 }
    
    window_start = 0
    p_length = p.length
    
    (0...s.length).each do |window_end|
        right_char = s[window_end]
        s_freq[right_char.ord - 'a'.ord] += 1
        
        if window_end >= p_length - 1
            if s_freq == p_freq
                result.push(window_start)
            end
            
            left_char = s[window_start]
            s_freq[left_char.ord - 'a'.ord] -= 1
            window_start += 1
        end
    end
    
    return result
end

                                            
impl Solution {
    pub fn find_anagrams(s: String, p: String) -> Vec<i32> {
        let s_chars: Vec<char> = s.chars().collect();
        let p_chars: Vec<char> = p.chars().collect();
        let mut res: Vec<i32> = Vec::new();

        if s.len() < p.len() {
            return res;
        }

        let mut p_freq: [i32; 26] = [0; 26];
        let mut s_freq: [i32; 26] = [0; 26];

        for &ch in p_chars.iter() {
            let idx = (ch as u8 - b'a') as usize;
            p_freq[idx] += 1;
        }

        for i in 0..s_chars.len() {
            if i >= p_chars.len() {
                let idx = (s_chars[i - p_chars.len()] as u8 - b'a') as usize;
                s_freq[idx] -= 1;
            }

            let idx = (s_chars[i] as u8 - b'a') as usize;
            s_freq[idx] += 1;

            if i >= p_chars.len() - 1 {
                if p_freq == s_freq {
                    res.push((i - p_chars.len() + 1) as i32);
                }
            }
        }

        res
    }
}

                                            
defmodule Solution do
  @spec find_anagrams(s :: String.t, p :: String.t) :: [integer]
  def find_anagrams(s, p) do
    len = String.length(p)
    p_dict = Enum.reduce(String.graphemes(p), %{}, fn c, acc -> Map.update(acc, c, 1, &(&1 + 1)) end)
    
    Enum.map(0..String.length(s) - len, fn i ->
      sub = String.slice(s, i, len)
      sub_dict = Enum.reduce(String.graphemes(sub), %{}, fn c, acc -> Map.update(acc, c, 1, &(&1 + 1)) end)
      Map.equal?(p_dict, sub_dict) && i
    end) |> Enum.filter(&(&1))
  end
end

To solve this coding challenge, we need to find all the start indices of the anagrams of string

p

within string

s

. An anagram of a string is formed by rearranging its letters, so for each substring of

s

with the length equal to

p

, we need to check if it is an anagram of

p

Explanation

Initial Checks : We begin by checking if
s

or
p

are empty, or if the length of
s

is less than the length of
p

. If any of these conditions is true, we return an empty list as it's not possible to have any anagrams.
Initial Setup : We initialize an empty list to store the starting indices of the anagrams. We then count the occurrences of each character in
p

(using a dictionary or any other suitable data structure) and do the same for the first
len(p) - 1

characters in
s

.
Sliding Window : We move a sliding window across
s

starting from
len(p) - 1

to the end of
s

. For each position of the window:

Include the character at the current position in our count.
Compare the current window's character counts with
p

's character counts. If they match, it means we found an anagram starting at the calculated index.
Exclude the character that is no longer in the window from our count.

Result Processing : Finally, return the list of starting indices where we found anagrams.

Detailed Steps

Check for Empty Inputs :

If
s

or
p

is empty or
len(s) < len(p)

, return an empty list because it is impossible to find any anagrams.

Initialize Result and Counts :

Create an empty list
result

to store the starting indices of anagrams.
Use a dictionary
p_count

to store the count of each character in
p

.
Initialize a dictionary
s_count

to store the count of characters in the initial window of
s

(first
len(p) - 1

characters).

Process Each Window :

Iterate from
len(p) - 1

to
len(s)

.

Add the character at the current index to
s_count

.
Compare
s_count

with
p_count

. If they are equal, append the starting index of the window to
result

.
Remove the character that exits the window from
s_count

.

Step-by-Step Explanation

Initial Checks :

If
s

is empty or
p

is empty or the length of
s

is less than the length of
p

, return an empty list.

Populate
p_count

and Initial
s_count

:

Calculate the frequency of each character in
p

and store it in
p_count

.
For the initial window (
s[0]

to
s[len(p) - 2]

), calculate the frequency of each character and store it in
s_count

.

Sliding Window Processing :

Loop over each character in the string
s

starting from the
len(p) - 1

index to the end.
Add the current character to
s_count

.
If the current window's character counts (
s_count

) match
p_count

, store the starting index of this window in the result list.
Remove the character at the start of the previous window from
s_count

.

Detailed Steps in Pseudocode:

                                            
// Check for Empty Inputs
if s is empty or p is empty or length of s < length of p:
  return empty list

// Initialize Result and Counts
p_count = frequency count of each character in p
s_count = frequency count of first len(p)-1 characters in s
initialize result as empty list

// Process Each Window
for i from len(p) - 1 to length of s - 1:
  // Include current character in s_count
  add 1 to s_count[character at index i in s]

  // Compare counts
  if p_count is equal to s_count:
    append i - len(p) + 1 to result

  // Remove character at start of previous window from s_count
  decrease s_count[character at index i - len(p) + 1 in s] by 1

  // If count becomes zero, remove the character from s_count
  if s_count[character at index i - len(p) + 1 in s] is zero:
    remove the character from s_count

// Return result
return result

This pseudocode provides a clear and detailed approach to solving the challenge while ensuring we explain each step thoroughly. It balances the logic needed to solve the problem with simplicity and clarity.