Make first string the Anagram of the second string?

Question

Each test case will contain a string having length len(S1)+len(S2), which will be concatenation of both the strings.The given string will contain only characters from a to z.

TASK :

find the minimum number of characters of the first string(wich will be the first half of the given string) that needs to be changed to make it an anagram of the second string.(wich will be the second half of the given string).

Input :

aaabbb

Output : 3

because 3 a(s) need to be replaced by 3 b(s) for the string1(aaa) to be an anagram of string2(bbb)

MY APPROACH :

If the string length is not even..then the 1st half cannot be the anagram of the second half ... So then print -1.

Otherwise :

1. I count the number of characters of each alphabet and store it an array of 26 elements..representing the number of repetitions of each alphabet from a-z.

2. I make 2 such arrays for the 2 strings.

3.I check with the two arrays to print the number of characters that needs to be changed. Since i need to make the 1st string the anagram of the second.. i ll check the two arrays .

Firststring[i] > SecondString[i] ... increment count !

This approach takes o(n^2) time. ( to traverse each of the string and form arrays for each).

I need a better solution !

Answer 1

A quite straightforward approach that runs in linear time (O(n)) is the following:

• Lets call the two substrings strA and strB for the discussion that follows. For each substring: map the characters in the string to an array holding the number of appearances of a specific character in the string. E.g., if assuming only non-capital letters in your string, you map the ASCII value of each character to the entries of an integer array of size 26 (English alphabet), shifting the ASCII value by -96 to attain mappings ASCII(a...z) -> index(0...25). Lets call these "number of appearances" arrays a and b in the discussion onwards, corresponding to substrings strA and strB, respectively.
• Thereafter, for each index i (in 0...25) where a[i] * b[i] > 0, the value min(a[i], b[i]) shows us the order of compliance in a and b, for the character associated with index i.
• The sum of the order of compliances give us the total compliance between the substrings strA and strB, and if this sum is equal to the length of these substrings (which have equal length, or return is -1), then the tw substrings strA and strB are anagrams of each other.

The following example shows this implementation in Swift, but I've used a purely imperative approach, so that it should readily be translatable to your favourite programming language of choice.

let myString = "aaabbb"
var myOutput: Int?
let numChars = myString.characters.count

if numChars%2 == 0 {

    let midIndex = myString.startIndex.advancedBy(numChars/2)
    let myLeftString = myString.substringToIndex(midIndex)
    let myRightString = myString.substringFromIndex(midIndex)

    let numDifferentLetters = 26 // asymptotic behaviour: assume n > numDifferentLetters
    var letterOccurencesLhs = [Int](count: numDifferentLetters, repeatedValue: 0) // < n
    var letterOccurencesRhs = letterOccurencesLhs // swift: arr value type, < n

    // n/2
    for charAscii in myLeftString.utf8 {
        letterOccurencesLhs[Int(charAscii)-96] += 1
    }

    // n/2
    for charAscii in myRightString.utf8 {
        letterOccurencesRhs[Int(charAscii)-96] += 1
    }

    // check order of compliance for each letter, w.r.t. numDiffLetters, < n
    var mySum = 0
    for i in 0 ..< numDifferentLetters {
        if letterOccurencesLhs[i] * letterOccurencesRhs[i] > 0 {
            mySum += min(letterOccurencesLhs[i], letterOccurencesRhs[i])
        }
    }

    myOutput = numChars/2-mySum

}
else {
    myOutput = -1
}

print("Output: \(myOutput!)") // 3 for "aaabbb"
                              // 2 for "aaabbbbbbbab"

    // Complexity: O(n)