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

  • gkeswani92 + 4 comments

    Python 3 solution:

    from collections import Counter
for _ in range(int(input())):
    s = input()
    l = len(s)
    if l % 2 == 1:
        print(-1)
    else:
        count = 0
        s1, s2 = Counter(s[:l//2]), Counter(s[l//2:])
        for char in s2:
            current = s2[char] - s1.get(char,0)
            if current > 0:
                count += current
        print(count)
    • particle + 1 comment

      I did too. This is supposed to be O(n) right?

      • particle + 2 comments

        If you want to utilize the Counter you can do (Counter(s1) - Counter(s2)).elements() this returns an iterator. So either convert to list then sum or use sum(1 for _ in iterator).

        • jellybeanfiend + 1 comment

          You can also do (Counter(s1) - Counter(s2)).values() to get the list of counts outright. Not a big difference but at least you can skip the step of converting to a list :)

          • hutcho66 + 0 comments

            Yep. A simple

            print(sum((Counter(s[:l//2]) - Counter(s[l//2:])).values()))

            works (after checking the length is even of course). No loop!

        • lunatic13 + 1 comment

          can u please explain the use of counter?

          • m_a_r_c_e_li_n_o + 0 comments

            Take a look at the C example below by "etayluz", followed by my explanation on why the counter is reduced by half at the end. It might help shed some light as to why a counter is used to solve the problem.

    • etayluz + 5 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]

      • arturs_aksjonen1 + 0 comments

        Fails at test case #8 (as of 07.2019) with 'wrong answer' like my own solution ;) I run all test cases within case #8 but with no luck.

    • lose311 + 0 comments

      This worked for me:

      from collections import Counter
n = int(input())
for _ in range(n):
    test = input()
    length = len(test)
    if len(test) % 2 != 0:
        print("-1")
    else:
        s1 = Counter(test[:length//2])
        s2 = Counter(test[length//2:])
        diff = s1 - s2
        print(sum(diff.values()))
    • peterkirby + 0 comments

      C++ Solution

      void countLetters(vector<int> &letters, string s, int begin, int end) {
    for (int i = begin; i < end; ++i)
        ++letters[s[i] - 'a'];
}

int numChanges(const string &s) {
    int length = s.length();
    if (length % 2) // odd
        return -1;
    int half = length / 2;
    vector<int> v1(26, 0), v2(26, 0), results(26, 0);
    countLetters(v1, s, 0, half);
    countLetters(v2, s, half, length);
    transform (v1.begin(), v1.end(), v2.begin(), results.begin(), [](int x, int y) { return abs(x - y); });
    int sum = accumulate(results.begin(), results.end(), 0);
    return sum / 2;
}