Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created July 25, 2016 05:46
Show Gist options
  • Save jianminchen/c5b6d09decd5f599392c0209e65b8236 to your computer and use it in GitHub Desktop.
Save jianminchen/c5b6d09decd5f599392c0209e65b8236 to your computer and use it in GitHub Desktop.
HackerRank - short palindrome - world codesprint #5 - first try - score 13/40, wrong answer, and also time out issue
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ShortPalindrome
{
class Program
{
static void Main(string[] args)
{
//string s = Console.ReadLine();
string s = "abbaab";
Console.WriteLine(getShortPalindrome(s, getAlphabetic(s)));
}
public static void testFunc()
{
int[] test1 = getAlphabetic("aaab");
string test2 = getPseudoString("abcdefac", 'a', 'c');
// test case 1: "011001" - 4
long count = countingPalindromes("0000001", true);
count += countingPalindromes("00000011", false);
}
public static int[] getAlphabetic(string s)
{
int[] res = new int[26];
if (s == null || s.Length == 0)
return res;
string arr = "abcdefghijklmnopqrstuvwxyz";
int TOTAL = 26;
int[] noAlph = new int[TOTAL];
char[] aA = arr.ToArray();
for (int i = 0; i < s.Length; i++)
{
int index = s[i] - 'a';
noAlph[index]++;
}
return noAlph;
}
/*
*
*/
public static long getShortPalindrome(string s, int[] input)
{
long res = 0;
int SIZE = 26;
long moduleValue = ((long)Math.Pow(10, 9) + 7);
for(int i=0; i<SIZE; i++)
{
int num = input[i];
long product = 1;
if(num>=4)
{
int index = 0;
while(index <=3)
{
product = (product * (num - index)) % moduleValue;
index++;
}
product /= 24;
res += product % moduleValue;
}
}
for(int i=0; i<SIZE; i++)
for(int j=i+1; j<SIZE;j++)
{
int val1 = input[i];
int val2 = input[j];
if (val1 < 2)
break;
if (val2 < 2)
continue;
char chA = (char)(i + 'a'); // bug001 - not val1, should be i,
char chB = (char)(j + 'a'); // bug002 - not val2, should be j
string s1 = getPseudoString(s, chA, chB);
res += countingPalindromes(s1, true) % moduleValue;
res += countingPalindromes(s1, false) % moduleValue;
}
return res;
}
/*
* using 0 and 1 to construct the string
* 1001
* 0110
*
*/
public static string getPseudoString(string s, char char0, char char1)
{
StringBuilder sb = new StringBuilder();
if (s == null || s.Length == 0)
return "";
char[] arr = new char[2] { char0, char1 };
for(int i = 0; i < s.Length; i++)
{
char index = s[i];
if(Array.IndexOf(arr, index) != -1)
{
if (index - char0 == 0)
sb.Append('0');
else
sb.Append('1');
}
}
return sb.ToString();
}
/*
* use two loops
*
* get 0110 pairs
* get 1001 paris
*
*/
public static long countingPalindromes(string s, bool first0)
{
if (s == null || s.Length == 0)
return 0;
int len = s.Length;
char compare = first0 ? '0' : '1';
char counting = first0 ? '1' : '0';
long count = 0;
long moduleValue = ((long)Math.Pow(10, 9) + 7);
for (int i = 0; i < len; i++ )
for(int j=i+3; j< len;j++)
{
char first = s[i];
bool firstOne = (first - compare) == 0;
if (!firstOne)
break;
char second = s[j];
bool secondOne = (second - compare) == 0;
if (secondOne)
{
// count how many 1 in-between
string s1 = s.Substring(i, j-i);
int oneC = getCompareCount(s1, counting);
count += (oneC * (oneC - 1) / 2) % moduleValue;
}
}
return count % moduleValue;
}
public static int getCompareCount(string s, char compare)
{
if (s == null || s.Length == 0)
return 0;
int count = 0;
for(int i=0; i<s.Length; i++)
{
if (s[i] == compare)
count++;
}
return count;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment