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)
what if
ReplyDeleteA=acbaccabccaaabbbcabcccb
B=abcc
your algo doesn't work.
Great article. I just post another article that has a full analysis: http://blog.gainlo.co/index.php/2016/04/08/if-a-string-contains-an-anagram-of-another-string/
ReplyDeleteIf size of B is 0, you're already done.
ReplyDeleteIterate over b - write each character to a hashmap with its frequency. if the character is already in the hashmap, increment the frequency.
iterate over set A... if the element exists in the hashmpa, decrement the frequency of the key by 1.
if keys are all 0 in the hashmap, it's an anagram.