# Sherlock and Anagrams

# Sherlock and Anagrams

gotRefill + 21 comments This problem made me question my existence. :(

etayluz + 34 comments I did as well at first. But it's easier if you break it into two parts:

- Traverse all possible substrings within string
- Check if any two substrings of equal length are anagrams

It's much more digestable that way.

C Solution:

`int check_anagram(char a[], char b[]) { int first[26] = {0}, second[26] = {0}, c = 0; while (a[c] != '\0') { first[a[c]-'a']++; c++; } c = 0; while (b[c] != '\0') { second[b[c]-'a']++; c++; } for (c = 0; c < 26; c++) { if (first[c] != second[c]) return 0; } return 1; } int main() { int t; scanf("%d", &t); while (t--) { char s[100]; char sub1[100] = {0}; char sub2[100] = {0}; scanf("%s", s); int count = 0; for (int len = 1; len < strlen(s); len++) { memset(sub1, 0, len); for (int i = 0; i < strlen(s) - len; i++) { strncpy(sub1, &s[i], len); memset(sub2, 0, len); for (int j = i + 1; j < strlen(s) - len + 1; j++) { strncpy(sub2, &s[j], len); if (check_anagram(sub1, sub2) == 1) { count++; } } } } printf("%d\n", count); } return 0;`

}

shubham_marathia + 0 comments [deleted]sandeepsr21 + 3 comments We can avoid one while loop inside check_anagram( ) function. As the lengths will be same. This will save few seconds of execution time.

while(a[c] != '\0')

{

`first[a[c]-'a']++; second[b[c]-'a']++; c++;`

}

AndreaR + 2 comments You can also optimize space by using a single array to count the char frequencies. Just add 1 for a and subtract 1 for b, then check if everything is at 0;

Jekus + 0 comments [deleted]coder1033 + 5 comments using

**collections**and**itertools**in**python 3**from collections import Counter from itertools import combinations def sherlockAndAnagrams(s): count = [] for i in range(1,len(s)+1): a = ["".join(sorted(s[j:j+i])) for j in range(len(s)-i+1)] b = Counter(a) count.append(sum([len(list(combinations(['a']*b[j],2))) for j in b])) return sum(count)

cassiofoliveira + 1 comment you don't need to actually list all combinations to count how many there are. There is an analytic formula to get that number n(n-1)/2 where n is the window(substring) size.

danisheazam + 1 comment Please Let me know why we are using n(n-1)/2

rmwenzel + 1 comment n(n - 1)/2 is "n choose 2", the number of distinct pairs of indices.

stu26code + 1 comment Also, for those of us who don't quickly and intuitively do algebra. The generic binomial formula is: n! / k! * (n-k)! If you use the generic formula, you're gonna get integer overflow, even with u128 integers (35!). But because the k is fixed:

n! / (2! * (n-2)!)

(1 / 2!) * (n! / (n-2)!)

And by definition of factorial n! => (n-2)! * (n-1) * n, so

(1/2) * ( ((n-2)! * (n-1) * n) / (n-2)! )

And the (n-2)! factorial cancels out, so we have:

(n * (n-1)) / 2

ghostuser + 0 comments Can you please explain the logical working of the second last statement of the code? (i.e. just before the return statement?)

cassiofoliveira + 1 comment I didn't go there, but there is probably a faster way to check for anagrams, we don't need to pay for the sort if we represent each string as an order independent hash.

coder1033 + 5 comments yes you're right, we don't need to list all combinations to count pairs. using your formula -

from collections import Counter def sherlockAndAnagrams(s): count = 0 for i in range(1,len(s)+1): a = ["".join(sorted(s[j:j+i])) for j in range(len(s)-i+1)] b = Counter(a) for j in b: count+=b[j]*(b[j]-1)/2 return int(count)

ken_wolf_email + 0 comments [deleted]advaithsurya + 0 comments Can you please explain this code? How did you proceed after coming till here? {a:2,b:2} {a:1,b:2} {a:1,b:1} {a:1}

After this, how do you proceed further? Precisely from Line 7th line, the 2nd for-loop.

fcnfelipe + 0 comments [deleted]fcnfelipe + 1 comment I've built a code in Swift based on your algorithm and that worked very well. Thanks! Here's the code:

func sherlockAndAnagrams(s: String) -> Int { let chars = Array(s) var nAnagrams = 0 for length in 0...chars.count-2 { var counter:[String:Int] = [:] for i in 0..<chars.count - length { let txt = String(chars[i...i+length].sorted()) counter[txt] = (counter[txt] ?? 0) + 1 } for c in counter { nAnagrams += c.value * (c.value - 1)/2 } } return nAnagrams }

applebuddy + 0 comments wow..

ranos + 0 comments Just incase if someone didnt understood,

`count+=b[j]*(b[j]-1)/2`

What he did is simply nC2, i.e Making combinations of size 2

ranjanasinha_89 + 1 comment Could someone explain "list(combinations(['a']*b[j],2))" part please? I understand that we are using combinations, but the [''a]*b[j] is stumping me.

rrohra200 + 3 comments the character "a" is used to form a combination which represents that the anagram of a particular substring taken into consideration exists i . e. the substring is present twice in the main string. ex :

['i', 'f', 'a',, 'l', 'u', 'h', 'k', 'q']

[[('a', 'a')], [],[],[] [], [], [], ('a', 'a')],]i and q are repeated twice, then we count the length , then sum up the len of list (in this case sum =2 as i and q form the anagram) then we append the sum to the count.

each iteration of i takes i length of substring. hope this helps

coder1033 + 0 comments yes, this is what i actually thought. But above formula makes it more efficient.

patrickhession97 + 1 comment could you please explain this I am still unsure why this part occurs "b[j]*(b[j]-1)/2"

bob_brahms + 2 comments That represents "n choose k" where n is b[j] and k is 2. https://en.wikipedia.org/wiki/Combination If b[j] is 5 , it's 5 * 4 / 2, or 10 which is the same as len(list(combinations([1] * 5, 2)))

You can also find more info on this by looking around for "binomial coefficients".

patrickhession97 + 1 comment That is honestly genius, thanks for your reply!!

kameldaniel + 0 comments yes indeed what the guy did is pure genius and your welcome :) if there is anything else i could do/explain,do not hesitate!

yudistirayoga97 + 0 comments Why did we assume that k=2?

aditya1574 + 0 comments what about repititions??

bob_brahms + 0 comments This is FTW! I didn't know about itertools.combinations, and it helped me debug my busted n_choose_k function I had used. Thanks!

mtbudish + 2 comments Thanks for the example. Based on this, I was able to write a solution in C# that works.

static int sherlockAndAnagrams(string s) { var matches = 0; for (int i = 1; i <= s.Length - 1; i++) { var a = new List<string>(); for (int j = 0; j <= s.Length - i; j++) { a.Add(new string(s.Substring(j, i).OrderBy(c => c).ToArray())); } var b = (from c in a group c by c into g select new { Key = g.Key, Count = g.Count() }) .ToDictionary(g => g.Key, g => g.Count); foreach (var v in b.Values) { matches += v * (v - 1) / 2; } } return matches; }

andrew_mcbrayer1 + 0 comments Sorting the string alphabetically before insertion into the map/dictionary is by far the simplest solution. props to you sir!

Not sure why this dosen't have more updoots

carlos_contreras + 0 comments WOW!! I really liked your solution. I made a shorter version based on your code:

public static int sherlockAndAnagrams(string s) { int counter = 0; for (int x = 1; x <= s.Length - 1; x++) { Dictionary<string, int> lista = new Dictionary<string, int>(); for (int y = 0; y <= s.Length - x; y++) { var cadena = new string(s.Substring(y, x).OrderBy(c => c).ToArray()); if (!lista.ContainsKey(cadena)) lista.Add(cadena, 1); else lista[cadena] += 1; } lista.Values.Where(w => w > 1).ToList().ForEach(v => { counter += v * (v - 1) / 2; }); } return counter; }

Chhatrapal_N + 0 comments [deleted]swagatikasahoo96 + 1 comment why we are doing like this ...a[c]-'a'??? what this line signifies ??

darksinge + 0 comments In C and C++,

`char`

s are represented as`int`

s under the hood, so you can do stuff like`int foo = 1 - 'a';`

.Using this idea, they create an array of 26 elements -- one element for each letter of the alphabet -- then use

`a[c] - 'a'`

to calculate the index that the character`a[c]`

belongs to.Note that

`'a' - 'a'`

equals 0,`'b' - 'a'`

equals 1,`'c' - 'a'`

equals 2, ..., and`'z' - 'a'`

equals 25.So, if

`first[1]`

is 3, that means there are 3 "b"'s in`a`

, and if`second[25]`

is 42, then that means there are 42 "z"'s in`b`

.

glegoux + 0 comments [deleted]alexr1993 + 1 comment it doesn't look like check_anagram("ab", "ba") would return true.

The lookup needs to compare the quantities of letters in some way without caring about the order, e.g. by sorting the substrings or passing in a lookup from char to quantity.

I'm not particularly familiar with C, so please correct me if I'm mistaken.

theprikshit + 0 comments it would return true. note that we are only storing the frequencies of each letter in both the strings and then comparing them one by one.

If the frequencies match for each digit, they are anagram

manjiri + 0 comments nice way of checking whether 2 strings are anagram of each other

ankcrimson + 0 comments You rock

yerzhik + 1 comment any other solutions not brute forcing like this? I did the same way: just iterating through all possible substring pairs and it worked

peterkirby + 9 comments Yes, it is possible to do better. This passes all tests in 0.01s. I guess I assumed that the tests would be harder.

https://www.hackerrank.com/challenges/sherlock-and-anagrams/submissions/code/21304431

Takeaways: (1) you can use "accumulator" arrays to store the number of occurences of each letter from 0 to an index, in O(N). Then you can lookup the number of letters between i and j in O(1) subsequently, by taking a difference. (2) You can use these to create an array of 26 integers for each substring, noting the count of each letter, which only needs to be done once, in O(N^2), because there are N*(N+1)/2 substrings. (3) You can sort this array once, which is therefore done in O(log N * N^2), which is the time complexity. (4) You can then go through this array once, counting the number of times there is a repeated anagram (equal arrays). (5) Finally you can get the final answer by summing R*(R-1)/2 for each repeated anagram, which is a math formula based on the sum from 1, 2, 3 .. R - 1. (See the link for an implementation in C++.) I think you could do better than this if you replaced the sort with a hash table (C++ unordered_map) for counting.

wendyzhuang_88 + 0 comments you write nice code.

RobertsN + 0 comments Also can be done slightly differently (non brute-force) See [url]https://www.hackerrank.com/challenges/sherlock-and-anagrams/submissions/code/23800700 [/url]

RogerB + 2 comments Yes, you can use a hashmap to get a solution that runs in O(N^2). You just have to do some little tricks in order to efficiently get hashcodes for the count arrays. https://www.hackerrank.com/challenges/sherlock-and-anagrams/submissions/code/23455764

RobertsN + 2 comments I didn't use a hashmap. I coded the logic for possible combinations using repeated chars (in pairs) and the distance between them (and to the right of the second without reaching a new repetition of the same char).

RogerB + 1 comment Looking at your solution, it looks like it runs in O(N^3). You compare each substring of equal length. There are O(N^2) such substrings, and each comparison takes O(N), leading to a total running time of O(N^3).

I took a different approach. I used hashing to effectively partition each substring into equivalence classes, based on the counts of the different characters they contained. Because I reuse calculations from one substring to another, this approach takes O(N^2), and is asymptotically more efficient. Take a look at the code I submitted, linked in my original post, to see exactly what I did, and why it's more efficient.

RobertsN + 1 comment Though I'm not an expert in On calculations, I don't this it's up to an O(N^3). Undoubtedly my code can probably be optimized a bit more, but I dare say that since I DON'T compare all O(N^2) substrings and actually don't test the ones I know will produce anagrams, code running should on average be a lot lower than O(N^3). Maybe a worst case scenario might be such but definitely not an average one such as in the tests.

I do a lot of culling pre-calculation and minimize the amount of substrings to test.

1st I eliminate all unnecessary weeds (sequences of characters which don't repeat) replacing them with a single char. 2nd I build pair sets of the same char (call it A) (one pair for AA, 3 pairs for AAA, 6 pairs for AAAA, etc.)

with A (x is an arbitrary qty of other chars): * AxA automatically has pair A,A * AxA automatically has Ax, xA (no anagram checking in either case)

Only then, taking AxxxxAyyyy (and 1st substring ALWAYS starting with the 1st A AND ALSO x is more than 1 char between A's, AND ALSO skip the above "automatic" anagram Axxx, xxxxA) will I: * search for anagramatic substrings within xxxxAyyyy which match against Axxxx but: DON'T include another "A", and are shorter than the length of Axxxx. Also watch out for falling off the end of the string.

This thins out a lot of unnecessary anagram checks. I don't have the test sets (and I'm not going to resign 5 hackos for each) to see how many times I actually do an anagram check.

Using C++ (I imagine from your profile you're more java oriented so times are not really comparable) the running times for my solution are:

Test Case 0 & 1: 0s

Test Case 2: 0.02s

Test Case 3: 0.16s

Test Case 4: 0.05s

Test Case 5: 0.12s

RogerB + 1 comment Your culling methods do definitely make your algorithm run faster, but only by a constant factor. We can say that your culling method weeds out some percentage of the substrings to check. Let's say it weeds out half, just so we have a number to work with. If you match 0.5N substrings, that takes O((0.5N)^2) = O(0.25N^2) = O(N^2) time, and each comparison takes O(N), so it still takes O(N^3), even though it's four times faster than it would be without the culling. What I can do some time is download your code, make some random input strings of different lengths and do experimental complexity analysis of both solutions. I'll post an excel sheet with the results in a couple of days.

I like this discussion. It's interesting.

RogerB + 2 comments I just finished the empirical complexity analysis. Actually, according to my results, your algorithm runs in O(N^4). I don't understand your code well enough to say why that is, though.

I generated an input consisting of 100 randomly initialized strings from length 10 to 1,000. I modified both of our codes slightly to output their running times in addition to the actual answer. On very small inputs, your code ran faster, (probably because of the language difference) but it took about 6 minutes on an input of length 1,000. With my hashing method, that input was processed in about a third of a second. You can check out all of my data and the analysis that I did in my excel file:

https://drive.google.com/file/d/0ByaGnKfMhkJLN1R3NzJ6SVRCNjA/view?usp=sharing

RobertsN + 0 comments Thanks, I'll check it out. Maybe I can improve on the solution. I'll post here if I find a better solution than my posted one.

RogerB + 0 comments [deleted]

nick_patenode + 1 comment I'm not sure, but I think your hash scheme is not wholly valid.

I think it could have a collision between two sets of letters wherein one has:

(37 of a single letter, lets say 'b')

and the other has

(a single of a letter that is one higher than the previous letter, so 'c')

Because of the way that you modify the hashcode.

You could skirt around this by tracking the number of items in a count. Or by using the products of unique prime numbers (See Fundamental Theorem of Arithmetic)

RogerB + 1 comment Short version: Yes, my method has collisions. So does the product of unique primes method. And that's okay, and even expected.

Any hashing method comes with the risk of collisions, with the exception of certain special cases where there are only a small number of predetermined possible unique instances. Most hash map implementations have a way to handle these collisions gracefully, with techniques like chaining. The trick is to make it unlikely that two unique objects have the same code, because it's impossible to ensure that unique objects have unique codes. For example, if you have [2^32 + 1] objects, it is guaranteed that you will have at least one collision, because you are mapping your objects onto the 32 bit integers, which has a domain of cardinality 2^32.

Let's look at the product of unique prime numbers method you proposed. (I'm assuming that you meant 'a'->2, 'b'->3, 'c'->5, 'd'->7, 'e'->11, etc.) The empty string "" has hash code 1, as a base case. The string "a" has hash code 2, because 1*2=2. The string "aa" has hash code 4, because 2*2=4. The string "aaa" has hash code 8, because 4*2=8. ... The string of 30 'a's has hash code 1073741824, because 536870912*2=1073741824. The string of 31 'a's has hash code -2147483648, because 1073741824*2=-2147483648. The string of 32 'a's has hash code 0, because -2147483648*2=0 The string of 33 'a's has hash code 0, because 0*2=0 ...

While the products of unique prime numbers method does yield unique numbers when working with the natural numbers, when working with 32 bit integers, (which form a commutative ring) overflows happen and you can have two unique sets of characters with the same hash code.

Addendum: I just noticed that you mentioned "because of the way that you modify the hashcode." Java's method of hashing strings (as lists of characters, not as sets of characters, like I did with my modification) has some good examples of simple hash collisions. For example, "Aa" and "BB" both have hash code 2112.

pc_bulukin + 0 comments You can solve the problem with overflow when multiplying primes by using BigInteger.

alexv2 + 0 comments Thanks for helping out! Here is the Javascript version: http://dpaste.com/39GXVZW

lonewolff + 0 comments i thought of the same but then thought to try brute force... Didn't even expect to pass all .. worked like a charm.. :)

addicted_abhi + 0 comments very good analysis

decfabrice + 0 comments You can use an unordered_map of (string,int) where the signature strings have 26 characters. C++ has a predefined hash for strings. This works because S has <= 100 characters, so that character counts for each character fit within an 8-bit char.

mikefromscratch + 0 comments @peterkirby I'd love to check your submission but that link doesn't point to it anymore. Any chance you can repost it here?

Cheers,

bgreenfield + 0 comments i was thinking the same thing, but the accumulator would be doing a difference of 26 elements each time i wanted that while the lenght of the entire string is 100 or less. seems like no time saving there.

dcsriram07 + 0 comments [deleted]vivek_reddy + 0 comments what is it's time complexity

CodeAA + 1 comment Didn't work for me for Python. Encountered TLE. But surely, does work for C/C++.

CodeAA + 1 comment Code even worked fine with Python 2. Is Python 2 faster than Python 3?

Varun_Rathi0623 + 0 comments [deleted]

golugupta + 0 comments thanx for your solution...

RobertsN + 2 comments Shorter in c++, saves one loop):

`bool CheckAna(string & s, int start1, int start2, int len) { int let[26] = {0}; bool result = true; for (int n = 0; n < len; n++) { let[s[start1+n]-'a']++; let[s[start2+n]-'a']--; } for (int n= 0; n <26; n++) { if (let[n] != 0) { result = false; break; } } return result; }`

P.D. haven't yet looked for a way to properly format the code in the posting

P.D. 2. Appears that code must start with a tab before each line (?)

Harika99 + 1 comment Heyy i jus can't understand why 'a' was used in this case.In which way it helps here. Could you please explain??

chidiimals + 1 comment Subtracting by 'a' gives an integer from 0 to 26. Each distinct character of the substring will have a unique position ranging from 0 to 26 and the value will correspond to the frequency of the character. Think of it as a map

avansharma + 0 comments I understood how it works. But I am saying, It was difficult to come up with that idea at first place.

karan_fantasial1 + 0 comments dude!! did this pass all the test cases.

iweizmeisk + 0 comments [deleted]iweizmeisk + 1 comment //check_anagram optimised.

`int check_anagram(char a[], char b[]) { int first[26] = {0}; if(strlen(a)) != strlen(b)) return 0; while (a[c] != '\0') { first[a[c]-'a']++; first[b[c]-'a']--; } for (c = 0; c < 26; c++) { if (first[c]>0 || first[c]<0) return 0; return 1; }`

souravbid321 + 0 comments you can easily check for if (first[c] != 0) return 0;

giaym + 0 comments [deleted]AndreaR + 0 comments I basically implemented the same thing in C# and Linq. Unfortunatelly the perf sucks and I lost. Arrays it is from now on.

suvm3 + 0 comments I can't understand how the memset() is working here,can u plz explain

positivedeist_07 + 0 comments Could u pls explain me what u did in the main()? I'm not familiar with memset and stuff :(

bazuka_ + 0 comments can you please explain me what will be the answer for "iiqq" and "abba".

joyjitpaul + 0 comments Why is memset required here?

alihashir4799 + 3 comments C++:

int sherlockAndAnagrams(string a){ // Complete this function int ana = 0; int diff = 1; for(int i=0;i<a.size()-1;i++){ vector<string> substrings(0); for(int j=0;j<a.size()-diff+1;j++){ substrings.push_back(a.substr(j,diff)); } for(int j=0;j<substrings.size();j++){ sort(substrings[j].begin(),substrings[j].end()); } for(int x=0;x<substrings.size();x++){ for(int y=x+1;y<substrings.size();y++){ if(substrings[x]==substrings[y]){ ana++; } } } diff++; } return ana; }

connerza + 0 comments Ahh I didn't even consider sorting before adding to the map for some reason. Cheers.

daiict_201712020 + 0 comments [deleted]emattics + 0 comments Noticed in examining the code - not that it will affect it much, but little pieces - the

for(int x=0;x

x can only be x < substrings.size() - 1, since y takes from x+1 to substring.size & the for will not occur.

avansharma + 0 comments How did you come up with that idea of finding anagram strings like that ?

eloyekunle + 6 comments Does not time out for Python 2 and 3:

def sherlockAndAnagrams(string): hash_table = dict() hashes = dict() def prime_map(c): 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) return primes[ord(c) - ord(a)] def get_hash(s): if s in hashes: hash_val = hashes[s] else: hash_val = 1 for c in s: hash_val *= prime_map(c) hashes[s] = hash_val return hash_val def save_hash(hash_val1, s): hash_val = get_hash(s) if hash_val1 == hash_val: if hash_val in hash_table: hash_table[hash_val] += 1 else: hash_table[hash_val] = 1 lenS = len(string) for length in range(1, lenS): for i in range(0, lenS - length): substr1 = string[i:i+length] hash1 = get_hash(substr1) for j in range(i + 1, lenS - length + 1): substr2 = string[j:j+length] save_hash(hash1, substr2) return sum([v for (k, v) in hash_table.items()])

stabgan + 1 comment There were 2 downvotes when I saw it . I upvoted it . It works perfectly . A little error is you have to change ord(a) to ord('a') .

The dudes who downvoted this post or will downvote my post are plain illiterate son of bitch .

Long live python and thanks eloykunle for this awesome hashing implementation

claudioct + 0 comments Upvoting thanks to you. ;)

Faker88Si + 0 comments there is runtime error on ur code bro

boiko_ivan + 0 comments Nice idea to hash with prime numbers. And to cache them to speed up processing.

peter_s_vdm + 1 comment Hey, 1 improvement that can be made that changes the runtime from O(n^3) to O(n^2), essentially removing the highest-nested

`for`

loop. my code:def strhash(s): h = 0 for c in s: h += hash(c) return(h) def seqsum(n): return int((n**2 + n) / 2) def sherlockAndAnagrams(s): count = 0 for l in range(len(s)): counter = dict() #l is length of substr. for i in range(len(s)-l): hashed = strhash(s[i:i+l+1]) if hashed not in counter: counter[hashed] = 1 else: counter[hashed] += 1 for k,v in counter.items(): if v > 1: count += seqsum(v-1) print(count) return count

Additional comment about my code, I know it assumes it won't encounter any strhash collisions (: but it passed all the tests

holpet + 1 comment It works perfectly, thank you! Could you please tell me what exactly the seqsum function does though? And why is it 'v-1'? I can't really see it in there.

nahi_torres + 0 comments Probably too late but in any case, function

**seqsum**is a simplified version of the combination formula c(n, r) with r = 2.

RobertsN + 0 comments Very good concept. I really liked it although I already solved the challenge with a different algo.

josef_klotzner + 0 comments a lot of effort. Besides stabgan already told you, that you have a little mistake (ord (a) instead of ord ('a')), this solution takes 4 times longer than using itertools combinations and Counter. -> downvoted

17manan + 0 comments C++ .Al test cases accepted For people who okay with a worse time complexity but which still passes all test cases. This is O(n^3logn) I think.

tjb295 + 1 comment Could you explain what substracting 'a' in the line First[a[c] - 'a'] performs in C?

RobertsN + 1 comment Converts a char (where a= ascii97) to a zero based integer. This way First[0] will be used for 'a', First[1] will be used for 'b', etc.

This makes the array smaller rather than having to use 123 positions, you can use just 26.

tjb295 + 0 comments Excellent, thank you for your explanation

fynx_gloire + 0 comments Hi, thx for your solution post but I do not believe you are getting all of he substrings of the passed in value. eg, if the passed in value is (a,b,c,d) then you are looking at substrings: abcd bcd cd d according to your nested for loops. What happened to substring ab? or abc, or a?

peter_hrvola + 0 comments I had the same solution of main and for anagrams I used dict with number of letters and the python version was just to slow

hacohen_yotam + 0 comments It says that a string might be up to a length of 100 chars. All possible substrings are 2^100 substrings. Doesn't it time out?

kushmnaik + 0 comments thank bro you made my day

ddlogesh + 0 comments Inspired from

**etayluz**clue but with little optimisation!`int sherlockAndAnagrams(string s){ int i, j, k, m, len, count = 0; len = s.length(); string a[len], x, y; for(i=1; i<len; i++) { m = len-i; for(j=0; j<=m; j++) a[j] = s.substr(j, i); for(j=0; j<m; j++){ for (k = j + 1; k <= m; k++) { if (a[j] == a[k]) count++; else if(i >= 2){ x = a[j]; y = a[k]; sort(x.begin(), x.end()); sort(y.begin(), y.end()); if (x == y) count++; } } } } return count; }`

andrew_pashkin + 0 comments Nested loops - not good, increases solution complexity.

resquer + 0 comments while (a[c] != '\0') { first[a[c]-'a']++; c++; }

This can be sped up by trading some space efficiency and using a cache since this part is executed multiple times for the same input.

That solution in Python looks like this:

@functools.lru_cache(100) def get_counts(s): return collections.Counter(s) def check_if_anagrams(one, two): return get_counts(one) == get_counts(two)

iGanja + 0 comments Even with this advice, my head is spinning! I'll get it though. I agree it's a medium complexity, but the logic is far from easy.

JulioLeme + 1 comment hahahahahah , good

mhorowitzgelb + 1 comment This can't be right. It's too brute force theres got to be a better way.

dariorvsso + 1 comment No. For this number of combinations, the brute force IS the better way: it gives you an easier to understand algorithm.

daltonrenaldo + 2 comments yet, I get timeout in Ruby...

MaxHeap + 0 comments use a Hash , and save the freq of every subsrting that would do it

zzurang + 1 comment Here is a one ruby implementation

def anagram_pairs_count(str) substrs = Hash.new() for l in 0..(str.length - 1) for h in l..(str.length - 1) substr = str[l..h] substrs[substr.length] ||= Hash.new(0) substrs[substr.length][substr.chars.sort.join] += 1 end end total = 0 substrs.each do |substr_length, anagram_to_count| pairs_count_list = anagram_to_count.values.map do |cnt| (cnt * (cnt - 1)) / 2 end total += pairs_count_list.reduce(&:+) end total end

RodriguezLucha + 0 comments def sherlockAndAnagrams(str) counter = Hash.new(0) (1...str.length).each do |len| str.chars.each_cons(len) do |substr| counter[substr.sort.join] += 1 end end counter.values.map { |n| n * (n - 1) / 2 }.reduce(:+) end

theprikshit + 2 comments I am having a hard time believing that brute force is the solution for this problem

imranraad + 0 comments String length is only 100. And Test case only 10. So brute force gets accepted. Even with 1000 characters string will get pass with frute force solution.

kamaru_sama + 8 comments in Python , using dict ( or map):

T = int(input().strip()) for a0 in range(T): s = input().strip() anag = 0 map = {} for i in range(len(s)): for j in range(len(s) - i): s1 = ''.join(sorted(s[j:j + i + 1])) map[s1] = map.get(s1, 0) + 1 for key in map: anag += (map[key] - 1) * map[key] // 2 print(anag)

bluewhale8202 + 0 comments amazing!

bluewhale8202 + 12 comments Your algorithm is O(N^3 logN) though because sorting takes O(NlogN) time. You can imporve it like this.

from collections import Counter def count_anagrams(string): buckets = {} for i in range(len(string)): for j in range(1, len(string) - i + 1): key = frozenset(Counter(string[i:i+j]).items()) # O(N) time key extract buckets[key] = buckets.get(key, 0) + 1 count = 0 for key in buckets: count += buckets[key] * (buckets[key]-1) // 2 return count

I tested this and it runs much faster on larger inputs.

kamaru_sama + 0 comments Nice Idea

Ashishgup + 1 comment I implemented the solution in a similar manner in C++ [O(N^3 logN)]. How would you reduce the NLogN part to N in C++?

Here is my code: https://www.hackerrank.com/challenges/sherlock-and-anagrams/submissions/code/34745972

bluewhale8202 + 0 comments sort(str.begin(),str.end());

this part takes O(NlogN) time because It is a comparison sort according to C++ docs. If you use an counting sort instead, you will achieve O(N) time sorting even though I'm not sure C++ standard library provides you a counting sort function.

Basically, you don't even need to sort it. If you can come up with a hash function which only considers numbers of occurences of each letter, not position, you can get by. That is 'abc' and 'cba' should be considered to be the same seed. I kinda did this thing in my code.

I'm not good enough at C++, so I don't think I can write you a succinct code snippet for it.

nhaley + 0 comments Thanks, this helped with my php version.

nd_niteshdwivedi + 1 comment Your code produces output 4 for 'ifailuhkqq' whereas the answer is 3

qwerty_1234 + 0 comments it should be 4 right ? iq and iq are anagrams

JJJason + 1 comment Nice idea. But frozenset operation generate an

**unordered**sequence. For example is**frozenset({('a', 2), ('b', 2)})**equals to**frozenset({('b', 2), ('a', 2)})**fujii + 1 comment And that's what you want.

avansharma + 0 comments [deleted]

nyartsgnaw + 0 comments AMAZING frozenset

rgriffin12321 + 0 comments Nice job. My implementation was similar, but I ended counted all values in counter which were greater than 1 during each iteration.

def sherlockAndAnagrams(s): counts = 0 for i in range(len(s)): substrings = ["".join(sorted(s[idx:idx+i+1])) for idx in range(0, len(s))] counts += sum([(v - 1) * v // 2 for _,v in collections.Counter(substrings).items()]) return counts

vitor_alquati + 2 comments Could someone explain me why increment counter like this:

count += buckets[key] * (buckets[key]-1) // 2

instead of:

count += buckets[key]//2

ckybonist + 1 comment Could you explain this formula by graph (the link you provided)?

justintteng + 0 comments Explained in this comment.

lt879 + 0 comments It's the combo (N,2) if there are 2 item then C(2,2) = 1 if 3 then C(3,2) .....

julie_larson + 0 comments [deleted]julie_larson + 1 comment Thank you, the frozenset trick is great

Can you explain the reasoning behind this line:

`count += buckets[key] * (buckets[key]-1) // 2`

bethpv + 0 comments If you have 3 instances of 'ab', the total number of anagram pairs is 2+1 = 3. In general, if you have n instances the number of anagram pairs is n-1 + n-2 + ... + 1. That simplifies to n*(n-1)/2 (they're actually the triangular numbers https://en.wikipedia.org/wiki/Triangular_number)

sohaibfarooqi + 1 comment I modified you solution to use Counter:

`from collections import Counter def sherlockAndAnagrams(s): anagrams = 0 c = Counter() for i in range(len(s)): combos = ["".join(sorted(s[j:j+i+1])) for j in range(len(s) - i)] c.update(combos) for k in c: anagrams += (c[k] - 1) * c[k] // 2 return anagrams`

kamilliano + 0 comments from collections import Counter # Complete the sherlockAndAnagrams function below. def sherlockAndAnagrams(s): counter = 0 for chunk in range(1, len(s)): arr = ["".join(sorted(s[i:i+chunk])) for i in range(0, len(s)) if i+chunk <= len(s)] c = Counter(arr) for key in c: counter += (c[key] * (c[key] - 1)) // 2 return counter

Took me the whole afternoon to realise that to use formula

`n * (n-1)/2`

and to use`sorted`

instead of combination of`ord`

and whatnot....

adityavyas1603 + 0 comments This is awesome!

akshaypandita201 + 0 comments good job

an09mous + 0 comments [deleted]an09mous + 0 comments I got exactly similar solution

def sherlockAndAnagrams(s): count=0 dict={} n=len(s) for i in range(n): for j in range(n-i): sub=''.join(sorted(s[j:j+i+1])) try: dict[sub]+=1 except: dict[sub]=1 for i in dict: count+=dict[i]*(dict[i]-1)//2 return count

unnatsingh5 + 0 comments how did you came up with that update rule for

`anag`

?guptashubu123 + 0 comments Explain the code plz!!!!

fynx_gloire + 0 comments Hi, thx for your solution post but I do not believe you are getting all of he substrings of the passed in value. eg, if the passed in value is (a,b,c,d) then you are looking at substrings: abcd bcd cd d according to your nested for loops. What happened to substring ab? or abc, or a?

Also can you explain the part where you are doing a*(a-1)/2?

Regards

bytamous + 0 comments But when you figure it out it is so satisfying :).

manuparmar35 + 0 comments you are not alone who thinks that

brainiak + 0 comments Well, what I learnt is we should always try brute first before letting the question question our own existence.

My simple c++ brute sol:

#define ll int #define all(a) a.begin(),a.end() void solve(){ string s,p; cin>>s; ll n=s.length(),c=0; for(ll i=1;i<n;i++){ map<string,ll> mp; for(ll j=0;j<n-i+1;j++){ p=s.substr(j,i); sort(all(p)); mp[p]++; } for(auto x:mp){ if(x.second>1){ c+=(x.second-1)*(x.second)/2; } } } cout<<c<<endl; }

mcgonigb + 15 comments I found it a lot easier to think about sorting substrings and using a map so that the key for anograms are the same : E.g. ab & ba both have key ab after sorting

`// Complete the sherlockAndAnagrams function below. static int sherlockAndAnagrams(String s) { HashMap<String, Integer> map = new HashMap<String, Integer>(); // Keep track of how many anagrams we've seen int totalCount = 0; // Generate all substrings (N^2) for(int i = 0 ; i < s.length(); i++) { for(int j=i+1 ; j <= s.length(); j++) { String currentSubString = s.substring(i,j); // Sort all strings E.g. ab & ba both == ab now char[] chars = currentSubString.toCharArray(); Arrays.sort(chars); currentSubString = String.valueOf(chars); // If sorted substring has been seen before if(map.containsKey(currentSubString)) { // Check how many times we've seen it and add that amount to the count int value = map.get(currentSubString); totalCount=totalCount+value; // Increment the times we've seen the string map.put(currentSubString, value+1); } else { // Never seen it before = insert and set to 1 to indiciate we've now seen it map.put(currentSubString, 1); } } } return totalCount; }`

alilow1 + 1 comment Thanks for the easy to understand solution.

I think with Java 8 the code can be compacted a little

int value = map.getOrDefault(currentSubString, 0); if (value > 0) { totalCount += value; } map.put(currentSubString, ++value);

tsdoycheva + 1 comment Is it necessary to check if value > 0 or we can just add it to totalCount? If we add 0 to totalCount nothing changes and all tests passed. But I'm not sure which option is more complex.

I'm talking about code like that:

int value = map.getOrDefault(currentSubString, 0);

totalCount += value;

map.put(currentSubString, ++value);

kruegernet + 1 comment map.merge(currentSubString, 1, (a,b) -> a + b)

I think this is most concise.

thiagotigaz + 0 comments This is even more concise :D map.merge(currentSubString, 1, Integer::sum)

pardeepsharma_d1 + 1 comment Awesome solution bro. Don't know how you guys think this much clear solution. I just stuck on thinking the substring part then give up on this problem :(

Thanks for your effort.

fzheng8 + 0 comments LOL

sandro101 + 1 comment I really didnt think this solution would work but it does. Can't quite understand how adding on to the total how many times you have seen the anagram does the same thing as nCr where n and r are total times seen and r is 2 for the pairs

kudos4mvijesh + 0 comments That is exactly what nC2 is - if you breakdown the general formula of nCr replace r with 2 - it comes to n*(n-1)/2 which is equal to the sum of all positive integers till (n-1)

prithvi_97 + 0 comments Genius. I didn't thing about sorting a char arrray. I was trying to build a new hash function to map all anagrams to the same Integer location and then do an nC2 on the count of all substrings. (n*(n-1)/2) Thanks for the way easier solution.

shivangi3490 + 0 comments nice easy to understand. thanks

shaileshntikhe + 1 comment does this work? where is condition to check if two strings are anagram?

artem_chumak + 0 comments He checks that both strings contain exactly the same chars. He builds an array of chars and sorts it. And then compares the resulting strings ex.

"abb" - > ['a', 'b', 'b'] -> sort -> ['a', 'b', 'b'] -> "abb" "bba" - > ['b', 'b', 'a'] -> sort -> ['a', 'b', 'b'] -> "abb" (therefore anagrams)

artem_chumak + 0 comments Great! Same as mine except that I didn't realize that you can do n!/[k!(n - k)!] as you are building the map of anagram groups.

tat_vam_asi + 0 comments The second loop should be

for(int j=1; j<=s.Length-i; j++){

It only worked for me after changing the second loop.

fzheng8 + 0 comments [deleted]fzheng8 + 1 comment Why add this? currentSubString = String.valueOf(chars);

seifert_felix + 0 comments Later on, you want to use the sorted String as a key for the HashMap.

String.valueOf(chars) creates a String out of the char-Array. It is stored in the variable currentSubString.

borakoks + 1 comment This code works but I couldn't understand how this sorting logic works for example; abc and bca would be same when sorted however they are not anagrams.

kameldaniel + 0 comments yes they are if there is a substring(or the stirng itself) abca,so u make a substring abc and add it to the hashmap and then at some point ur going to make a substring bca which is an anagram of abc. I personally couldn't understand the: totalCount=totalCount+value;

kameldaniel + 0 comments thank u very much for sharing,just one question, what is the complexity of this method,is it O(n^2) or O(n^3)?

a18wheeler + 2 comments I literally had almost this exact code except for one little thing that made it error...

`totalCount = totalCount + value`

. I was thinking that you would add one each time you found a matching string, so my code used`totalCount++`

instead. Can anyone explain why adding the values of the map works?Also, here's my identical (working) Java code for those who are interested.

static int sherlockAndAnagrams(String s) { // go through a string and add every value to a hashmap HashMap<String, Integer> map = new HashMap<>(); // total of anagrams int total = 0; // for each key, add one to value for(int i = 0; i < s.length(); i++) { for(int j = i+1; j <= s.length(); j++) { // get substring and sort it! String sub = s.substring(i,j); // sorting the string char tempArray[] = sub.toCharArray(); Arrays.sort(tempArray); sub = new String(tempArray); if(map.containsKey(sub)){ // adds one to last value int oldValue = map.get(sub); // total++ WRONG total+=oldValue; // RIGHT map.put(sub, ++oldValue); } else { // add to map if not seen map.put(sub, 1); } } } return total; }

Benjii + 1 comment is there a solution in java with better complexity than this or not ?? why we are sorting??

josef_klotzner + 0 comments you can bring described algorithms to any programming language. Just do it. I don't think that you expect just to copy and paste a public solution and then say: "i have done it" :) I realized it with python 3. All inclusive. Precomputation, Memoization and so on. Instead of standard sorting (O (n log ni) i used much faster method counting sort (O (n) as this is possible in this case, precompute that and process results in cooperation with mathematic formulas by subtract count lists of r and l position and process them. As already said. Don't expect that i will post it. This is a competition site where you should learn yourself, otherwise you are lying to yourself and cheat against the others ^^

oliveira_carlos + 0 comments I have the same question.

e_himsi + 0 comments Nice solution.

szykov + 0 comments c# implementation of your code:

static int sherlockAndAnagrams(string s) { var dic = new Dictionary<string, int>(); var count = 0; foreach (var substring in getSubstring(s)) { Console.WriteLine(substring); if (dic.ContainsKey(substring)) { var value = dic[substring]; count += value; dic[substring] = value + 1; } else { dic.Add(substring, 1); } } return count; } static IEnumerable<string> getSubstring(string s) { for (var i=0; i<s.Length; i++) { for (var j=1; j<=s.Length - i; j++) { var substring = s.Substring(i, j); var chars = substring.ToCharArray(); Array.Sort(chars); yield return new string(chars); } } }

hellomici + 0 comments Hi all,

If you have time, feel free to comment on what do you think about my Python3 code: https://www.hackerrank.com/challenges/sherlock-and-anagrams/forum/comments/465694?h_l=playlist&slugs%5B%5D=interview&slugs%5B%5D=interview-preparation-kit&slugs%5B%5D=dictionaries-hashmaps

tundereuben + 0 comments Lol, you got me laughing...

I'm trying to figure the logic too.

pablo_tsanchez + 2 comments A solution in 2 lines of code. Thanks, Python.

`from collections import Counter def sherlockAndAnagrams(s): substrings = [''.join(sorted(s[i:j+1])) for i in range(len(s)) for j in range(i, len(s))] return sum([(v*(v-1))//2 for _, v in Counter(substrings).most_common()])`

stabgan + 1 comment nice . How much time it took for you ?

pablo_tsanchez + 0 comments After giving up for brute force... 10 minutes. Before that, I really cannot tell. I guess at least one hour.

jnicolich + 0 comments You can also use itertools combinations:

from collections import Counter from itertools import combinations def sherlockAndAnagrams(s): substrings = [''.join(sorted(s[i:j])) for i, j in combinations(range(len(s)+1), 2)] substring_counts = Counter(substrings) return sum([v*(v-1)//2 for _,v in substring_counts.items()])

charles_p_leon + 0 comments Its not exactly a fast solution but I used this same idea. Here is my python code for it. First I generate a dictionary with a k,v pair which is (length of substring, substrings of the same length). Then I generate all the possible substrings and for each one I sort them and them find out if the sorted substring is already in the array of sorted substrings of the same length. If so we've found another anagram so we increment the anagram counter. After generating all the substrings we will also have the number of anagrams.

def sherlockAndAnagrams(s): anagrams = 0 substrings = {i: [] for i in range(1, len(s) + 1)} for i in range(0, len(s)): for j in range(i+1, len(s) + 1): substr = " ".join(sorted(s[i:j])) for k in range(0, len(substrings[j-i])): if substrings[j-i][k] == substr: anagrams += 1 substrings[j-i].append(substr) return anagrams

reda_alb2 + 1 comment This is my Java solution, see if it will help you understand it better. Any feedback will be greatly appreciated.

static int sherlockAndAnagrams(String s) { int n = s.length(); //This will control the length of each substring each pass. //For the first pass, it will 1(every single character), next 2, every 2 blocks of characters etc.. int I = 1; int numOfAnagrams = 0; //Looping through n - 1 (number of substrings). //2nd loop, looks at each substring for each length. //3rd loop loops through the rest of the substrings of the same length as s1. for(int i = 0; i < n - 1; i++) { for(int j = 0; j <= n-I; j++) { String s1 = s.substring(j, j + I); for(int k = j+1; k <= n-I; k++) { String s2 = s.substring(k, k + I); if(checkAnagrams(s1, s2)) numOfAnagrams++; } } I++; } return numOfAnagrams; } static boolean checkAnagrams(String s1, String s2) { //Creating 2 HashMaps to hold each char of strings and their frequncies, then checking if they are equal or not. If they are equal, they are anagrams. Map<Character, Integer> s1Map = new HashMap<>(); Map<Character, Integer> s2Map = new HashMap<>(); char[] s1Chars = s1.toCharArray(); char[] s2Chars = s2.toCharArray(); //s1 and s2 will be coming in as the same length. for(int i = 0; i < s1.length(); i++) { Character s1Char = Character.valueOf(s1Chars[i]); Character s2Char = Character.valueOf(s2Chars[i]); if(s1Map.containsKey(s1Char)) s1Map.put(s1Char, s1Map.get(s1Char) + 1); else s1Map.put(s1Char, 1); if(s2Map.containsKey(s2Char)) s2Map.put(s2Char, s2Map.get(s2Char) + 1); else s2Map.put(s2Char, 1); } return s1Map.equals(s2Map); }

masandnikita + 0 comments the time complexity of this will be O(n^3)?

blackjar72 + 0 comments I didn't find it too hard to find a way that basically worked, O = n^3 (due to n^2 / 2 comparisions which are inividually linear) -- but find myself at a total loss to find an

way that doesn't fail some tests by timing out. I hate the way some of these problems can make me feel dumb.*efficient*abhilashvenky + 0 comments Lol Dude

vayuj + 0 comments This how i approached: 1. Generated all Subsequence of the String and stored in a List. 2. Sorted the Strings in the list alphabetically 3. Find Equality of the same strings 4. Time Complexity: O(n^2)

yalok698 + 0 comments true brother cheetah hai tu (>_<)

vivekmnjl + 0 comments I was feeling dumb until i saw this comment. I still feel the same but now i have some social validation :D

bbakewai + 0 comments **I think this will help you**import java.util.HashMap; import java.util.Map; import java.util.Arrays;

class SherlockAndAnagrams { static int getAp (int n) { return (n * (n + 1)) / 2; }

`static String stringSort (String s) { char chars[] = s.toCharArray(); Arrays.sort(chars); return new String(chars); } static HashMap<String, Integer> getSubStrings (String s) { HashMap<String, Integer> map = new HashMap<>(); for (int i=0; i<s.length(); i++) { String sub = "" + s.charAt(i); if (map.containsKey(sub)) { map.put(sub, map.get(sub) + 1); } else { map.put(sub, 1); } for (int j=i+1; j<s.length(); j++) { sub = stringSort(sub + s.charAt(j)); if (map.containsKey(sub)) { map.put(sub, map.get(sub) + 1); } else { map.put(sub, 1); } } } return map; } static int sherlockAndAnagrams(String s) { HashMap<String, Integer> map = getSubStrings(s); int count = 0; for (Map.Entry entry : map.entrySet()) { int value = (int) entry.getValue(); if (value > 1) { count += getAp(value - 1); } } return count; } public static void main(String[] args) { String str = "cdcd"; System.out.println(sherlockAndAnagrams(str)); }`

}

samveen + 0 comments I wrote a horribly inefficient solution in perl, and it worked! That made me question my existance!!!!

sub sherlockAndAnagrams($) { my ($st)=@_; my @a=split(//, $st); my %h; for(my $i=0; $i<=$#a; ++$i) { for(my $j=0; $j<=$#a-$i; ++$j) { my $s=join "", sort(@a[$j..$j+$i]); if(exists($h{$s})) { $h{$s}+=1; } else { $h{$s}=1; } } } my $totals=0; for my $k (keys(%h)) { $totals+= $h{$k}*($h{$k}-1)/2; } return $totals; }

iGanja + 0 comments Starting to for me as well. Ugh!

fionalmatters + 20 comments I got horribly confused with this one so thought I would shed some light on the practice questions:

abba

a|0,0| a|3,3|

b|1,1| b|2,2|

ab|0,1| ab|2,3|

abb|0,2| abb|1,3|

4

abcd

0

ifailuhkqq

i|0,0| i|3,3|

q|8,8| q|9,9|

afi|0,2| afi|1,3|

3

hucpoltgty

t|6,6| t|8,8|

gt|6,7| gt|7,8|

2

ovarjsnrbf

r|3,3| r|7,7|

jnrs|3,6| jnrs|4,7|

2

pvmupwjjjf

p|0,0| p|4,4|

j|6,6| j|7,7|

j|6,6| j|8,8|

j|7,7| j|8,8|

jj|6,7| jj|7,8|

mpuv|0,3| mpuv|1,4|

6

iwwhrlkpek

w|1,1| w|2,2|

k|6,6| k|9,9|

ekp|6,8| ekp|7,9|

3

Zero indexed showing initial string, numbers and each match.

zac_c_petit + 1 comment I wouldn't have known where to begin with this problem without your comment. Thanks!!

lvkhoa + 0 comments Me too =.=

varghesearunct + 0 comments Thanks for your explanation..

fbertani + 0 comments Thanks for your explanation!!

bala93 + 0 comments Thank You. Your comment helped me understand the problem better.

smitavishal + 0 comments Thanks for clarifying the question

SErAphLi + 0 comments [deleted]s21fargo + 0 comments Thank you! the 1st example was not enough to understand this question.

vids_sampath + 0 comments Thanks a lot for your exlanation.

alphamale_me + 1 comment thanks for explaination. one question. why is there no jj[6,8] and jj[7,8]

SidraS + 0 comments Much needed explanation. Thanks!

imeshuek059 + 0 comments Thanks a lot :)

imeshuek059 + 0 comments is test case 1 it should be a |1,3|,|3,1| and..... right?

tchen21 + 0 comments Thank you!!

paridhichoudhary + 1 comment How is jnrs|3,6| jnrs|4,7| an anagram in example ovarjsnrbf ?

clavicl + 0 comments [3,6]rjsn is an anagram of [4,7]jsnr

sidmishraw + 0 comments Thanks for providing a clear explanation :)

friendsdivya + 0 comments Thanks for your explanation!

tofallis + 0 comments Excellent clarification thank you. Much more useful than actual solutions being posted here.

Tanisha23 + 0 comments This really helped. Thnx a lot.!!

nd_niteshdwivedi + 0 comments Very good description bro.

kratos_hellblade + 0 comments Thanks for the answer , couldn't figure out one of the samples

rumshenoy + 2 comments It would help if the second example was explained instead of leaving it as an excercise. One example is not enough to understand the whole question.

neurotoxins + 0 comments exactly, sample inputs and outputs are there for a reason

Ma77o + 0 comments Couldn't agree more with this sentiment!!

Tunabrain + 0 comments This is a terribly worded problem.

The only explanation is a link to the wiki page on anagrams - no explanation as to what exactly an unordered anagrammatic pair is. The only example that is explained is a) symmetric b) only contains four letters.

I can just about guess what is asked here, but this is an awfully worded question and should either be improved or removed.

youfeng243 + 0 comments This problem not describe clearly，so sad！！

tommyogp + 11 comments I manged to solve this by a very simple math formula. First, I group and count frequencies of duplicated substrings . Then, the number of anagram pairs of a substring can be calculated by vertices-edges relationship.

E.g. For input,

1 aaa

I would have a HashMap like,

[{a:3}, {aa:2}]

Then,

'a' appears at 11,22,33 => number of pairs = (3)(3-1)/2 = 3

'aa' appears at 12,23 => number of pairs = (2)(2-1)/2 = 1

Just sum them up to get total number of anagram pairs for 'aaa'. E.g. 3+1 = 4

completebs91 + 0 comments ^^^Awesome solution. Helped me out a ton.

hbzahid + 0 comments [deleted]maximshen + 0 comments Great math thought. Hope java can have cool built in permutation one day as python

harshnigm + 0 comments [deleted]pcg79 + 1 comment I'm following you until the last part.

`(x)(x-1)/2`

Where do you get that from?tommyogp + 1 comment You may refer it from here: https://en.wikipedia.org/wiki/Complete_graph

Look at verticies and edges.

sgoyal534 + 0 comments you can think it as nC2 i.e. selecting 2 items from a lot of strength 'n'.

Gozalishvili_ANZ + 0 comments Hello. I can suggest such principle; count the number of dublicate anagram substrings and than sum the numbers of k[n]; where k[n] denotes the number of pairs from n dublicates; k[0]=0; and k[n]=k[n-1]+n-1; you are using maybe the similar method but can you tell me what method u are using for counting duplicates? i only get all substrings and sort characters in it and than used map for counting duplicates.

here is code: http://ideone.com/EXeL2V

prateekjoshi + 0 comments Acc to you, for string "iwwhrlkpek" answer should be 4 but its 3.

shahpujan1992 + 0 comments can u plz describes the same for input -> abba. so the keys are sorted in HashMap for this problem?

zac_c_petit + 0 comments Vertices-edges relationship, known in math as bionomial coefficients :) https://en.wikipedia.org/wiki/Binomial_coefficient

Nopethisis + 0 comments can u please explain your logic on string abbabaab

sumanconstantin + 0 comments Two anagrams are not just two duplicated strings, the second string can also have letters in random order.

Do you sort the strings before grouping them?

calcagnofa + 3 comments My Python 3 Solution

def sherlockAndAnagrams(s):

`dict={} count=0 for i in range(len(s)): for j in range(i+1,len(s)+1): list1= list(s[i:j].strip()) list1.sort() transf=''.join(list1) if transf in dict: count+=dict[transf] dict[transf]=dict[transf]+1 else: dict[transf]=1 return count`

kbenriquez + 0 comments Genius!

vicalegc + 5 comments My solution is very similar to yours. I just want to include it here for reference:

def sherlockAndAnagrams(s): anagram_dict = {} count = 0 for i in range(1, len(s)): for j in range(len(s)-i+1): current_sorted = str(sorted(s[j:j+i])) if (current_sorted not in anagram_dict): anagram_dict[current_sorted] = 1 else: count += anagram_dict[current_sorted] anagram_dict[current_sorted] += 1 return count

sebruiz + 2 comments I found your solution to be the most elegant. Here is in Javascript:

function sherlockAndAnagrams(s) { let count = 0; // Size of our sliding window for (let i = 1; i < s.length; i++) { let found = {}; // Starting index of our sliding window for (let j = 0; j + i <= s.length; j++) { let substr = s.substr(j, i); substr = substr.split('').sort().join(''); if (found[substr]) { count += found[substr]; found[substr]++; } else { found[substr] = 1; } } } return count; }

sak7258 + 0 comments Gracias tenia la idea de como hacer el .split('').sort().join(''); y luego comparar. pero no tenia idea de como armar los for para que pasara por todas las palabras

jacksmirk + 0 comments I think you are missing a step. You have to check is substr is not '' otherwise you will get a lot of occurrencies.

function sherlockAndAnagrams(s) { let count = 0; for (let i = 0; i < s.length; i++) { let found = {}; for (let j = 0; j + i <= s.length; j++) { let substr = s.substr(j, i); if (substr) { substr = substr.split('').sort().join(''); if (found[substr]) { count += found[substr]; found[substr]++; } else { found[substr] = 1; } } } } return count; }

shayanhusaini + 1 comment Here is the PHP version of your solution

function sherlockAndAnagrams($s) { $anagrams = 0; $found = []; for($i=0; $i<strlen($s); $i++) { for($j = 0; ($j + $i) <= strlen($s); $j++) { $sub = substr($s, $i, $j); $sub = str_split($sub); sort($sub); $sub = implode('', $sub); if($sub != '') { if(isset($found[$sub])) { $anagrams += $found[$sub]; $found[$sub]++; } else { $found[$sub] = 1; } } } } return $anagrams; }

mohamedelsayed0 + 0 comments nice it helps.

deshwaljaivardh1 + 0 comments by far easiest to understand---thnx

blackhaj + 1 comment Very nice solution, thanks for posting.

Can you explain why you use:

`count += anagram_dict[current_sorted]`

As opposed to:

`count += 1`

I know it is right but I can't get my head around why it needs to be like that.

Many thanks, Henry

lars1607 + 0 comments Each newly encountered set of characters can form anagrammatic pairs with all previously encountered matching sets of characters. For example, if you encounter the fourth occurrence of a certain set of characters, you can form six pairs between them (0 + 1 + 2 + 3 = 6).

renato314159 + 0 comments I'm having so much trouble figure out the logic on this.

anyway you can help me see this?

yulian_karapetk1 + 0 comments Your solution translated to

**JavaScript**:const dictionary = {}; let count = 0; for (let i = 0; i < str.length; i++) { for (let j = i + 1; j < str.length + 1; j++) { const transformed = str.slice(i, j).trim().split('').sort().join(''); if (dictionary[transformed]) { count += dictionary[transformed]; dictionary[transformed]++; } else { dictionary[transformed] = 1; } } } return count;

mps_ymg + 2 comments OMG, I've confused anagrams and palindroms! ))

cvasco + 0 comments HA I definitely did this too at first. Most of the examples are palindromes except "fai" "ifa" but I didn't notice that. oh well... I learned to read the question carefully!!

sumanconstantin + 0 comments I failed Facebook's interview for VR department, just because of this exact problem and similar challange.

shashank_30 + 3 comments c++ code

int check_anagram(string ,string); int main(){ int t; cin>>t; for(int x=0;x<t;x++){ int count=0;//No. of pairs string s; cin>>s; for(int i=1;i<=s.length();i++){ vector <string> str;//to store the sub string of length i for(int j=0;j+i<=s.length();j++){ str.push_back(s.substr(j,i));// pushing the sub string of length i } for(int p=0;p<str.size();p++){ for(int q=p+1;q<str.size();q++){ if(check_anagram(str[p],str[q]))count++; } } } cout<<count<<endl; } return 0; } int check_anagram(string s1,string s2){ int a1[26]={0},a2[26]={0}; for(int i=0;i<s1.length();i++){ a1[s1[i]-'a']++; } for(int i=0;i<s2.length();i++){ a2[s2[i]-'a']++; } for(int i=0;i<26;i++){ if(a1[i]-a2[i]!=0){ return 0;//two strings are not anagram } } return 1;//two strings are anagram }

positivedeist_07 + 1 comment Phew!! Got a C/C++ coder :) hey could u pls explain me the main() part?? I'm totally stuck with it. It'd be really helpful if u explained.

shashank_30 + 0 comments Yes sure. First you calculate the no. of substrings starting from length=1 by using

for(int i=1;i<=s.length();i++)

Then you are pushing them in vector 'str' by using

for(int j=0;j+i<=s.length();j++)

By using this below logic you are comparing two strings in str vector for anagrams and maintaining the count.

for(int p=0;p<str.size();p++) for(int q=p+1;q<str.size();q++)

Then again the same procedure for length=2, length=3 till length =string`s length-1.

Hope you got it.

mansher_kang + 0 comments [deleted]mansher_kang + 0 comments your check_anagram function is quite sufficient

good job!!

Sort 785 Discussions, By:

Please Login in order to post a comment