Algorithms
Find anagrams of a string in another string
Given a string (haystack) and a pattern (needle). Find all the anagrams of the pattern that are contained in the string.
For example: str = “abateatas” and pattern = “tea”. Then output should be the anagrams of “tea” contained as a substring in str. So, the desired output = {“ate”, “eat”, “tea”}.
A quick bruteforce solution would be to find all the anagram of the pattern and then check which are contained as a substring of str. This is a costly string matching operation including exponential cost for generating all the anagrams.
Sliding Histogram Approach – O(n) time O(1) space
Notice that when we find an anagram starting from i we might potentially find another starting from i+1 if character count distribution remains same. For example, text = “abaab” and pattern = “aba”. We can see both of the strings have same character count distribution i.e. histogram ([a=2,b=1,c=0,..]) for first m characters, where m=length of pattern. If we remove first character ‘a’ and add 4th character ‘a’ then histogram remains same ([a=2,b=1,c=0,..]).
So, we can create a fixed length (=size of the pattern) sliding window histogram for characters in text string and check if the window equals to the pattern histogram at each position of the text. We keep sliding the window to right one position and check if the window equals to patten histogram. This is linear time algorithm if the alphabet size of the strings is finite (for example 256 character set). Below is the implementation of the idea in O(n) time and O(1) space.
private static boolean equalHistogram(int[] hist1, int[] hist2){
for(int i = 0; i < hist1.length; i++){
if(hist1[i] != hist2[i]){
return false;
}
}
return true;
}
public static int searchAnagramSubstring(String text, String pattern){
int count = 0;
int n = text.length();
int m = pattern.length();
if(n < m | m == 0 | m == 0){
return 0;
}
int textHist[] = new int[256];
int patHist[] = new int[256];
//initial histogram window of size m
int i = 0;
for(i = 0; i < m; i++){
patHist[pattern.charAt(i)]++;
textHist[text.charAt(i)]++;
}
//search the pattern histogram in a sliding window of text histogram
do{
//O(1) time check as array size is constant
if(equalHistogram(textHist, patHist)){
System.out.println("anagram found : "+text.substring(i-m, i));
count++;
}
//slide the text histogram window by 1 position to the right and check for anagram
textHist[text.charAt(i)]++;
textHist[text.charAt(i-m)]--;
} while(++i < n);
return count;
}
Mathematical Approach – O(n) time O(1) space
But I have an elegant solution in my mind which only takes O(n) time and constant space if the haystack is significantly larger than the needle. The idea is to get a unique hash for all the anagrams of a word by calculating the product of unique prime values assigned to each of the characters. After calculating product value of the needle, we will find pair of indices (i, j) in the haystack such that product of characters from i to j is equal to the product value of needle. Then the substring at i of length (j-i+1) is an anagram.
In order to find such a product we can observe that product of an array[0..n] of characters is divisible by product of any subarray[i..j] starting at i. So, product(i..j) = product of needle if only if product(0..j)/product(0..i) = product of needle. In other words if product(0..j) is divisible by product of needle then there is an anagram ending at position j.
For example, haystack = “cababaacaa” and needle =”aab” then product(needle) = 2*2*3 = 12.
Now, product(0..3) = 5*2*3*2 = 60 which is divisible by 12. So, we found an anagram of length 3 ending at position 3 i.e “aba”. Similarly we will find “baa” ending at position 6.
For our convenience let’s suppose that the string contains alphabet from a english dictionary i.e. There are 26 letters only. However, the solution will work with any number of characters.
- Assign each of the 26 letters a unique prime number i.e. {‘a’=>2, ‘b’=>3, ‘c’=>5, ‘d’=>7, ‘e’=>11, …, ‘l’ = 37, …, ‘s’ => 67, …. ,’t’ => 71,…. ‘z’ => 101}. In order to extend, If we have 8 byte character then we will use first 256 primes.
- All the anagrams of a word will have the same UNIQUE product of primes assigned to each character. For example: prod(“tea”) = prod(“tae”) = prod(“eat”) = prod(“eta”) = prod(“ate”) = prod(“aet”)= 71*11*2 = 1562. Find prime product of the needle.
- Now, go through each position of the haystack and find cumulative product at each position and keep the index of a cum-prod in a hashmap.
- while passing through the letters of the haystack check if the current cum-prod is divisible by the needle product value. If it is then it means we found an anagram! The anagram ends at the current position having a length equal to needle length. So, we can get the substring in relatively constant time if haystack size is significantly larger than the needle.
This is only O(n) time solution using constant space of the size of the alphabet list.
private static int primes[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
public static Set<String> findAnagramicSubString(final String str, final String pattern) {
final String haystack = str.toLowerCase();
final String needle = pattern.toLowerCase();
final Set<String> substrings = new HashSet<String>();
long needleKey = 1;
for (int i = 0; i < needle.length(); i++) {
needleKey *= primes[needle.charAt(i) - 'a'];
}
final Map<Long, Integer> cumprods = new HashMap();
long cumprod = 1;
for (int i = 0; i < haystack.length(); i++) {
cumprod *= primes[haystack.charAt(i) - 'a'];
if (cumprod % needleKey == 0 && cumprods.containsKey(cumprod / needleKey)) {
substrings.add(haystack.substring(i - needle.length() + 1, i + 1));
}
cumprods.put(cumprod, i);
}
substrings.remove(needle);
return substrings;
}
There could be a variant of this problem.
Given a dictionary and a word. Find all the anagrams of the given word in the dictionary.
Following is an O(n) solution with constant space. The idea is to create a hash function that will return same value for anagrams of a word. We can build such a hash using he character histogram of a word.
public class Dictionary{
private Set<String> dictionary = new HashSet<String>();
public void add(String word){
dictionary.add(word);
}
public void addAll(List<String> words){
dictionary.addAll(words);
}
public boolean remove(String word){
return dictionary.remove(word);
}
private String getKey(String str){
str = str.toLowerCase().trim();
int[] hist = new int[256];
for(int i = 0; i < str.length(); i++){
hist[str.charAt(i)]++;
}
StringBuilder sb = new StringBuilder();
for(int val : hist){
sb.append(val);
}
return sb.toString();
}
public int searchAnagram(String pattern){
int count = 0;
HashMap<String, List<String>> histogramMap = new HashMap<String, List<String>>();
for(String word : dictionary){
String key = getKey(word);
if(!histogramMap.containsKey(key)){
histogramMap.put(key, new ArrayList<String>());
}
histogramMap.get(key).add(word);
}
String searchKey = getKey(pattern);
List<String> res = histogramMap.get(searchKey);
if(res != null){
count = res.size();
System.out.print("anagrams in dict: ");
for(String s : res){
System.out.print(s+" ");
}
System.out.println();
}
return count;
}
}