Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created March 14, 2016 05:39
Show Gist options
  • Save jianminchen/f3c48ed9f3b16e8c5928 to your computer and use it in GitHub Desktop.
Save jianminchen/f3c48ed9f3b16e8c5928 to your computer and use it in GitHub Desktop.
HackerRank: String algorithm - Anagram - https://www.hackerrank.com/challenges/anagram
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Anagram
{
class Program
{
/*
* https://www.hackerrank.com/challenges/anagram
*
*/
static void Main(string[] args)
{
string s1 = Console.ReadLine();
int n = Convert.ToInt16(s1);
for(int i=0;i<n;i++)
{
string s = Console.ReadLine();
Console.WriteLine(getMinNumberToChange(s));
}
}
/*
* len(s1) + len(s2) >=1, and <= 10000
* 1 <= T <= 100
*
* string will contain only characters from a to z
*/
public static int getMinNumberToChange(string s)
{
if (s == null || s.Length == 0)
return -1;
int n = s.Length;
if (n % 2 == 1)
return -1;
int SIZE = 26;
int count = 0;
int[] sumA = getSumArray(s, 0, n/2-1);
int[] sumB = getSumArray(s, n/2, n-1);
for (int i = 0; i < SIZE; i++)
{
if (sumA[i] > 0)
// add count of chars in array sumA but not in sumB
count += (sumA[i] >= sumB[i]) ? (sumA[i] - sumB[i]) : 0; // axxbbbxx, axxb, a 1, b 1, x 2; bbxx, a 0, b 2, x 2
}
return count;
}
public static int[] getSumArray(string s1, int start, int end)
{
int SIZE = 26;
int[] sumA = new int[SIZE];
for (int i = start; i <= end; i++ )
{
sumA[s1[i] - 'a']++;
}
return sumA;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment