Skip to content

Instantly share code, notes, and snippets.

@priort

priort/Anagram.fs

Last active Feb 6, 2017
Embed
What would you like to do?
module Anagram
//Hackerrank problem
//Anagram
// Sid is obsessed with reading short stories. Being a CS student, he is doing some interesting frequency
// analysis with the books. He chooses strings and in such a way that .
// Your task is to help him find the minimum number of characters of the first string he needs to change to
// enable him to make it an anagram of the second string.
// Note: A word x is an anagram of another word y if we can produce y by rearranging the letters of x.
// Input Format
// The first line will contain an integer, , representing the number of test cases. Each test case will contain
// a string having length , which will be concatenation of both the strings described
// above in the problem.The given string will contain only characters from to .
// Constraints
// Output Format
// An integer corresponding to each test case is printed in a different line, i.e. the number of changes
// required for each test case. Print if it is not possible.
// Sample Input
// 6
// aaabbb
// ab
// abc mnop
// xyyx
// xaxbbbxx
// Sample Output
// 3
// 1
// -1
// 2
// 0
// 1
// Explanation
// Test Case #01: We have to replace all three characters from the first string to make both of strings
// anagram. Here, = "aaa" and = "bbb". So the solution is to replace all character 'a' in string a with
// character 'b'.
// Test Case #02: You have to replace 'a' with 'b', which will generate "bb".
// Test Case #03: It is not possible for two strings of unequal length to be anagram for each other.
// Test Case #04: We have to replace both the characters of first string ("mn") to make it anagram of other
// one.
// Test Case #05: and are already anagram to each other.
// Test Case #06: Here S1 = "xaxb" and S2 = "bbxx". He had to replace 'a' from S1 with 'b' so that S1 =
// "xbxb" and we can rearrange its letter to "bbxx" in order to get S2
let numOccurences (str:string) c = str |> Seq.filter ((=) c) |> Seq.length
let numChangesToMakeAnagram (str1Str2:string) =
if str1Str2.Length % 2 <> 0 then -1
else
let (str1, str2) =
(str1Str2.[0..(str1Str2.Length/2) - 1],str1Str2.[str1Str2.Length/2..str1Str2.Length - 1])
(Set.ofSeq str2)
|> Set.toArray
|> Array.map (fun c ->
let d = (numOccurences str2 c) - (numOccurences str1 c)
if d < 0 then 0 else d)
|> Array.sum
[<EntryPoint>]
let main argv =
let numStrings = int (System.Console.ReadLine())
[
for i in 1..numStrings do
yield System.Console.ReadLine() |> numChangesToMakeAnagram
]
|> List.iter (printfn "%A")
0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment