String A contains a substring which is anagram of String B ?

you are given two arrays. A of size n, B of size m. m is a very very small number compared to n. find out if A contains a substring which is anagram of B.


Approach1:
1. Sort B
2. maintain a window of length m and slide it along A
3. for each window do:
3.1 Sort the window O(mlogm)
3.2 Compare the sorted window with sorted B
3.3 If equal anagram found


T(n) = O(n*mlogm) but since m<<n T(n)~O(n)




Approach 2:
A = "dropoffprogrammingisgoodforhealth"
B = "ford"


find all the indices of characters in B string in A.
f = 5,6,24
o = 2,4,9,21,22,25
r = 1,8,11,26
d = 0,23


now find the indices for "f", "o", "r" and "d" such that they are consecutive.


In the above example we have 23, 24, 25, 26 - hence A contains a substring which is anagram of B.


If we can not find consecutive indices for all the characters in B, then A does not contain substring which is anagram of B.


What if B contains duplicate characters ? ie what if B = "fordo" in the above example ?


time complexity for above solution = O(n)

Print all the anagrams for a word from dictionary.

Imagine you had a dictionary. How would you print all anagrams of a word? What if you had to do this repeatedly? Could you optimize it?


Approach:
We need to develop a key for a given word such that all the words in an anagram set can be represented uniquely.
one way is to convert the word string to lowecase and sort the words lexicographically.
example: Tea, Eat, Ate will become: aet.
Then we can use a HashMap to store the anagram set, with "aet" as key and "Tea, Eat, Ate" as the list of words.


Another approach could be we can assign each letters from a..z a prime numbers (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, .. so on)
and then for any word, we can calculate its key as the multiples of all the prime number corresponding to characters in the word.


say tea = 71*11*2 = 1562
similarly eat and ate will yeild 1562. Now 1562 is the key in your hashMap and value will be the list of words - "tea, eat, ate";


a=2, b=3, c=5, d=7, e=11, f=13, g=17, h=19, i=23, j=29, 
k=31, l=37, m=41, n=43, o=47, p=53, q=59, r=61, s=67, t=71, 
u=73, v=79, w=83, x=89, y=97, z=101


If we have to do the operation repeatedly then we will preprocess and calculate all the anagrams sets in the dictionary and cache it.

Check if 2 strings are anagrams

Method to check if two given strings are anagrams or not.
public boolean isAnagram(String first, String second) {
if (null == first || null == second) {
return false;
}
int firstLen = first.length();
int secondLen = second.length();

if (firstLen != secondLen) {
return false;
}

char [] firstArr = first.toLowerCase().toCharArray();
char [] secondArr = second.toLowerCase().toCharArray();

Arrays.sort(firstArr);
Arrays.sort(secondArr);

for (int i=0; i<firstLen; i++) {
if (firstArr[i] != secondArr[i]) {
return false;
}
}
return true;
}