Created
March 14, 2016 05:39
-
-
Save jianminchen/f3c48ed9f3b16e8c5928 to your computer and use it in GitHub Desktop.
HackerRank: String algorithm - Anagram - https://www.hackerrank.com/challenges/anagram
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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