Created
July 25, 2016 06:14
-
-
Save jianminchen/894c9b723aa847f1a261658147e1ecaf to your computer and use it in GitHub Desktop.
HackerRank - shortPalindrom - world codesprint #5 - try to solve timeout issues, not resolved, new issue - run time error
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; | |
} | |
} | |
Dictionary<string, long> dict = new Dictionary<string, long>(); | |
Dictionary<string, long> dict2 = new Dictionary<string, long>(); | |
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); | |
if (dict.ContainsKey(s1)) | |
res += dict[s1] % moduleValue; | |
else | |
{ | |
res += countingPalindromes(s1, true, dict2) % moduleValue; | |
res += countingPalindromes(s1, false, dict2) % 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, Dictionary<string, long> dict) | |
{ | |
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); | |
long oneC = 0; | |
if (dict.ContainsKey(s1)) | |
oneC = dict[s1]; | |
else | |
{ | |
oneC = getCompareCount(s1, counting); | |
dict[s1] = oneC; | |
} | |
count += (oneC * (oneC - 1) / 2) % moduleValue; | |
} | |
} | |
return count % moduleValue; | |
} | |
public static long getCompareCount(string s, char compare) | |
{ | |
if (s == null || s.Length == 0) | |
return 0; | |
long 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