Discussion on Anagram Challenge

aquio 4 years ago+ 1 comment

Same idea in Swift times out in some of the test cases. Any optimization suggestions?

var t = Int(readLine()!)!

for _ in (0..<t) {
    var strArr = readLine()!.characters.map{String($0)}

    if strArr.count % 2 != 0 {
        print("-1")
    } else {
        var middle = strArr.count / 2
        var map = [String : Int]()

        for i in (0..<middle) {
            if map[strArr[i]] == nil {
                map[strArr[i]] = 1
            } else {
                map[strArr[i]] = map[strArr[i]]! + 1
            }

            if map[strArr[middle + i]] == nil {
                map[strArr[middle + i]] = -1
            } else {
                map[strArr[middle + i]] = map[strArr[middle + i]]! - 1
            }
        }

        var res = 0
        for (key, value) in map {
            res = res + abs(value)
        }

        print(String(res/2))
    }
}

peterkirby 4 years ago+ 1 comment

You could translate the logic more directly by using .utf8 on a string to get the ASCII codes, subtracting the ASCII value of 'a' (97), and using that to index an array of size 26 representing the letters and their counts (like the C/C++ examples posted here). It's possible that using the map and indexing it with strings is more expensive than doing that.

aquio 4 years ago+ 0 comments

Your suggestion has been really helpful! As you suggested, indexing a simple frequency array instead of a map results in better performance. Thanx!

Here is the working version for Swift:

var t = Int(readLine()!)!

for _ in (0..<t) {
    var strArr = Array(readLine()!.characters)

    if strArr.count % 2 != 0 {
        print("-1")
        continue
    }      

    var letter = [Int](count: 26, repeatedValue: 0)
    var count = 0

    for i in (0..<strArr.count / 2) {
        var charNum = Int(Array(String(strArr[i]).utf8)[0])
        letter[charNum - 97] = letter[charNum - 97] + 1
    }

    for i in (strArr.count / 2..<strArr.count) {
        var charNum = Int(Array(String(strArr[i]).utf8)[0])
        letter[charNum - 97] = letter[charNum - 97] - 1
    }

    for i in (0..<26) {
        count = count + abs(letter[i])
    }

    print(String(count / 2))

}