Sunday, March 25, 2012

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)

3 comments:

  1. what if
    A=acbaccabccaaabbbcabcccb
    B=abcc

    your algo doesn't work.

    ReplyDelete
  2. 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/

    ReplyDelete
  3. If size of B is 0, you're already done.
    Iterate 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.

    ReplyDelete