We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Algorithms
  3. Strings
  4. Anagram
  5. Discussions

Anagram

  • etayluz + 4 comments

    C Solution:

    int main() {

int t;
scanf("%d", &t);
while (t--) {
    char s[10000];
    scanf("%s", s);
    int len = strlen(s);
    if (len % 2 == 1) {
        printf("-1\n");
        continue;
    }

    int letter[26] = {0};
    int count = 0;
    for (int i = 0; i < len/2; i++) {
        char c = s[i];
        letter[c - 'a']++;
    }
    for (int i = len/2; i < len; i++) {
        char c = s[i];
        letter[c - 'a']--;
    }

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

    printf("%d\n", count/2);
}
return 0;

    }

    • yrelhan4 + 1 comment

      I am kinda having trouble understanding the count/2 part. An explanation would be good. Thanks.

      • m_a_r_c_e_li_n_o + 1 comment

        This method counts for differences on both strings, so the answer needs to be reduced by half since the question asks how many times ONE string needs to be modified to match the other. For example, with string "aaabbb", this method concludes that "aaa" doesn't match "bbb" and that "bbb" doesn't match "aaa", implying that 6 letters need to be modified for them to equal somehow (i.e. cccccc). However we just need one string to transform into another, so really only 3 letters need to be modified (i.e. "aaa" from first string becomes "bbb", thus matching the second).

        • Joker8 + 0 comments

          Instead of checking both first and second string. I checked only the first string and then didn't multiply the count by half.

    • brokenmystery + 0 comments

      used the exact same logic already. The small difference being i used letter2 for 2nd for loop and then calculated the difference

    • aquio + 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 + 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 + 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))

}
    • Sasintheran + 1 comment

      can you please explain the term...

      letter[c-'a']++;

      I can't understand this line...how its works? explain me please...

      • aquio + 0 comments

        letter is a frequency array - you count how many appearances of each letter of alphabet are there in your string. So, at letter[0] you have frequency for 'a', at letter[1] for 'b' etc. For example, if your c within the loop at some point is 'd', then 'd' - 'a' = 100 - 97 = 3, (100 and 97 are respective character codes) and you do required operation on letter[3]