String
7. Find All Anagrams in a String

Find All Anagrams in a String (opens in a new tab) Medium

Problem

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.

Example

Input: s = "cbaebabacd", p = "abc"

Output: [0, 6]

Summary

To solve this problem, we can use the sliding window technique along with a character frequency map. We will maintain a window of length p in the string s and compare the character frequencies in the current window with the character frequencies of the string p. If the frequencies match, the starting index of the window is added to the output list.

Solution

In TypeScript

function findAnagrams(s: string, p: string): number[] {
	const result: number[] = [];
	const pCharCount: Map<string, number> = new Map();
	const sCharCount: Map<string, number> = new Map();
 
	for (const char of p) {
		pCharCount.set(char, (pCharCount.get(char) || 0) + 1);
	}
 
	for (let i = 0; i < s.length; i++) {
		const char = s[i];
		sCharCount.set(char, (sCharCount.get(char) || 0) + 1);
 
		if (i >= p.length) {
			const removeChar = s[i - p.length];
			sCharCount.set(removeChar, sCharCount.get(removeChar) - 1);
			if (sCharCount.get(removeChar) === 0) {
				sCharCount.delete(removeChar);
			}
		}
 
		if (areMapsEqual(pCharCount, sCharCount)) {
			result.push(i - p.length + 1);
		}
	}
 
	return result;
}
 
function areMapsEqual(map1: Map<string, number>, map2: Map<string, number>): boolean {
	if (map1.size !== map2.size) {
		return false;
	}
 
	for (const [key, value] of map1) {
		if (map2.get(key) !== value) {
			return false;
		}
	}
 
	return true;
}

In Python

def findAnagrams(s: str, p: str) -> List[int]:
		result = []
		p_char_count = {}
		s_char_count = {}
 
		for char in p:
				p_char_count[char] = p_char_count.get(char, 0) + 1
 
		for i in range(len(s)):
				char = s[i]
				s_char_count[char] = s_char_count.get(char, 0) + 1
 
				if i >= len(p):
						remove_char = s[i - len(p)]
						s_char_count[remove_char] -= 1
						if s_char_count[remove_char] == 0:
								del s_char_count[remove_char]
 
				if are_maps_equal(p_char_count, s_char_count):
						result.append(i - len(p) + 1)
 
		return result
 
def are_maps_equal(map1, map2):
		if len(map1) != len(map2):
				return False
 
		for key, value in map1.items():
				if map2.get(key) != value:
						return False
 
		return True

Step-by-step explanation

  1. Initialize an empty result array to store the starting indices of anagrams found.
const result: number[] = [];
  1. Initialize two Maps pCharCount and sCharCount to store the character count of pattern p and substrings of s.
const pCharCount: Map<string, number> = new Map();
const sCharCount: Map<string, number> = new Map();
  1. Loop through the characters of p, incrementing their count in the pCharCount map.
for (const char of p) {
	pCharCount.set(char, (pCharCount.get(char) || 0) + 1);
}

  1. Loop through the characters of s with the index i.

    a. Increment the count of the current character char in the sCharCount map.
    b. If i is greater than or equal to the length of p, remove the character s[i - p.length] from the sCharCount map. If the character count becomes zero, delete the entry from the map.
    c. Check if the pCharCount and sCharCount maps are equal using the areMapsEqual function. If they are equal, add the starting index of the substring (i - p.length + 1) to the result array.

for (let i = 0; i < s.length; i++) {
	const char = s[i];
	sCharCount.set(char, (sCharCount.get(char) || 0) + 1);
 
	if (i >= p.length) {
		const removeChar = s[i - p.length];
		sCharCount.set(removeChar, sCharCount.get(removeChar) - 1);
		if (sCharCount.get(removeChar) === 0) {
			sCharCount.delete(removeChar);
		}
	}
 
	if (areMapsEqual(pCharCount, sCharCount)) {
		result.push(i - p.length + 1);
	}
}
  1. Return the result array containing the starting indices of anagrams found.
return result;

The areMapsEqual function checks if the two given maps have the same key-value pairs:

  1. Check if the size of the two maps is equal. If not, return false.
if (map1.size !== map2.size) {
	return false;
}
  1. Loop through the key-value pairs of map1. If the value of the current key in map2 is not equal to the value in map1, return false.
for (const [key, value] of map1) {
	if (map2.get(key) !== value) {
		return false;
	}
}
  1. If the function doesn't return false during the loop, return true to indicate that the maps are equal.
return true;

Complexity Analysis

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input string s. We use a single loop to iterate through the string s and maintain a window of characters.

Space Complexity

The space complexity of this solution is O(m), where m is the size of the character set. In this case, we use maps to store character frequencies for both p and the sliding window in s. The character set is limited to lowercase English letters, resulting in a maximum space complexity of O(26).

6. Longest Palindromic Substring8. Group Anagrams