-1

I was reading an algorithmic problem at http://learn.hackerearth.com/question/314/finding-non-anagramic-strings-in-a-list/

I came across the following claim:

Two strings (of same size) are anagrams of each other if and only if the sum and product of the characters of the two strings are same (treat A => 1, B => 2, ..., Z => 26).

I tried to prove this but I failed. Can someone prove this claim?

Steve M
  • 83
  • 7
  • Try doing it through induction – Abhishek Bansal Sep 12 '13 at 15:53
  • The claim is false. I found a counter example at http://stackoverflow.com/questions/14739186/a-possible-algorithm-for-determining-whether-two-strings-are-anagrams-of-one-ano?rq=1 – Steve M Sep 12 '13 at 15:54
  • @AbhishekBansal The strings should be of the same size. – Steve M Sep 12 '13 at 15:55
  • Actually that post deals with ASCII values though I won't be surprised if many such counter examples are found with this condition as well. – Abhishek Bansal Sep 12 '13 at 16:02
  • i'm not sure why your source would have thought it to be true. Length, sum and product give you three constraints. A length n string has n degrees of freedom, so we would expect to find lots of counter examples once n>3. And in fact, your example, without the leading As, is a counter example of length 3. – Teepeemm Sep 12 '13 at 17:22

2 Answers2

3

The claim is really false. Following is a counter example.

  • ABBI: Sum = 14, Product = 36
  • AAFF: Sum = 14, Product = 36
Steve M
  • 83
  • 7
0

As shown in the answer above this logic does not holds good. I would suggest to check if:

  1. Length of string 1=String 2
  2. if condition 1 is true then Sort String 1 and String 2 and compare them
fiddle
  • 1,095
  • 5
  • 18
  • 33