CODEWITHSUNDEEP
c#algorithm
user6048670
user6048670

Reputation: 2887

What is the flaw in my algorithm for determining how many letter replacements one string needs to be an anagram of another string?

I've been staring at this for a half hour and can't figure out where I'm going wrong! I'm getting obviously incorrect answers for count in some of the test cases. I've tested every subroutine of the program and it works as expected. So WTF?

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{    
    static void Main(String[] args)
    {
        int T = Int32.Parse(Console.ReadLine());
        for(int t = 0; t < T; ++t)
        {

            string str = Console.ReadLine();
            if(str.Length % 2 == 1) // str couldn't be split into halves
            {
                Console.WriteLine(-1);
                continue;
            }
            // determine how many replacements s1 needs to be an anagram of s2
            int n = str.Length / 2;
            string s1 = str.Substring(0, n);
            string s2 = str.Substring(n, n);
            int[,] counter = new int[26,2]; // counter[i,j] will be the # of occurences of the i-th letter
                                            // of the alphabet in string sj
            int ascii_a = (int)'a'; 
            for(int i = 0; i < n; ++i)
            {
                counter[(int)s1[i] - ascii_a, 0] += 1;
                counter[(int)s2[i] - ascii_a, 1] += 1;
            }

            // sum difference of occurences in each letter, and divide sum by 2
            int count = 0;
            for(int i = 0; i < n; ++i)
            {
                count += Math.Abs(counter[i, 0] - counter[i, 1]);
            }
            count /= 2; 

            Console.WriteLine(count);
        }
    }
}

Test input: 

aaabbb
ab
abc
mnop
xyyx
xaxbbbxx

My output:

3
0
-1
0
0
1

Expected output: 

3
1
-1
2
0
1

Upvotes: 0

Views: 48

Answers (1)

Tin Svagelj
Tin Svagelj

Reputation: 145

s2 is assigned as:

string s2 = str.Substring(n, n);

and I'm guessing you want to use:

string s2 = str.Substring(n, str.Length);

I think that should fix the problem you're having, but your current output is weirdly accurate for the first input

Upvotes: 1

Related Questions