Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created March 27, 2016 16:48
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/90c0eec6d8c3c5cd7f18 to your computer and use it in GitHub Desktop.
Save jianminchen/90c0eec6d8c3c5cd7f18 to your computer and use it in GitHub Desktop.
Sherlocks And Anagrams - HackerRank - C# solution
using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading;
// ()
public class Solver
{
int Fun(string s, int l, int r)
{
var ret = new int[26];
for (int i = l; i <= r; i++)
ret[s[i] - 'a']++;
int x = 0;
for (int i = 0; i < 26; i++)
x = x * 701 + ret[i];
return x;
}
public object Solve()
{
for (int tt = ReadInt(); tt > 0; tt--)
{
string s = ReadToken();
int n = s.Length;
int ans = 0;
var count = new Dictionary<int, int>();
for (int i = 1; i < n; i++)
for (int j = 0; j + i <= n; j++)
{
var key = Fun(s, j, j + i - 1);
if (!count.ContainsKey(key))
count[key] = 0;
count[key]++;
}
foreach (var p in count)
ans += p.Value * (p.Value - 1) / 2;
writer.WriteLine(ans);
}
return null;
}
#region Main
protected static TextReader reader;
protected static TextWriter writer;
static void Main()
{
#if DEBUG
reader = new StreamReader("..\\..\\input.txt");
writer = Console.Out;
//writer = new StreamWriter("..\\..\\output.txt");
#else
reader = new StreamReader(Console.OpenStandardInput());
writer = new StreamWriter(Console.OpenStandardOutput());
//reader = new StreamReader("game.in");
//writer = new StreamWriter("game.out");
#endif
try
{
// var thread = new Thread(new Solver().Solve, 1024 * 1024 * 128);
// thread.Start();
// thread.Join();
object result = new Solver().Solve();
if (result != null)
writer.WriteLine(result);
}
catch (Exception ex)
{
#if DEBUG
Console.WriteLine(ex);
#else
Console.WriteLine(ex);
throw;
#endif
}
reader.Close();
writer.Close();
}
#endregion
#region Read / Write
private static Queue<string> currentLineTokens = new Queue<string>();
private static string[] ReadAndSplitLine()
{
return reader.ReadLine().Split(new[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
}
public static string ReadToken()
{
while (currentLineTokens.Count == 0)
currentLineTokens = new Queue<string>(ReadAndSplitLine());
return currentLineTokens.Dequeue();
}
public static int ReadInt()
{
return int.Parse(ReadToken());
}
public static long ReadLong()
{
return long.Parse(ReadToken());
}
public static double ReadDouble()
{
return double.Parse(ReadToken(), CultureInfo.InvariantCulture);
}
public static int[] ReadIntArray()
{
return ReadAndSplitLine().Select(int.Parse).ToArray();
}
public static long[] ReadLongArray()
{
return ReadAndSplitLine().Select(long.Parse).ToArray();
}
public static double[] ReadDoubleArray()
{
return ReadAndSplitLine().Select(s => double.Parse(s, CultureInfo.InvariantCulture)).ToArray();
}
public static int[][] ReadIntMatrix(int numberOfRows)
{
int[][] matrix = new int[numberOfRows][];
for (int i = 0; i < numberOfRows; i++)
matrix[i] = ReadIntArray();
return matrix;
}
public static int[][] ReadAndTransposeIntMatrix(int numberOfRows)
{
int[][] matrix = ReadIntMatrix(numberOfRows);
int[][] ret = new int[matrix[0].Length][];
for (int i = 0; i < ret.Length; i++)
{
ret[i] = new int[numberOfRows];
for (int j = 0; j < numberOfRows; j++)
ret[i][j] = matrix[j][i];
}
return ret;
}
public static string[] ReadLines(int quantity)
{
string[] lines = new string[quantity];
for (int i = 0; i < quantity; i++)
lines[i] = reader.ReadLine().Trim();
return lines;
}
public static void WriteArray<T>(IEnumerable<T> array)
{
writer.WriteLine(string.Join(" ", array));
}
public static void Write<T>(params T[] array)
{
WriteArray(array);
}
public static void WriteLines<T>(IEnumerable<T> array)
{
foreach (var a in array)
writer.WriteLine(a);
}
#endregion
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment