Created
July 25, 2016 05:46
-
-
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
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 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