Last active
April 2, 2016 22:03
-
-
Save jianminchen/37e3c65f03f62dcdeb2e9634a11e0efa to your computer and use it in GitHub Desktop.
HackerRank - Reverse Shuffle Merge - Only passed one test case, failed most of them
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 ReverseMergeString | |
{ | |
class Program | |
{ | |
static void Main(string[] args) | |
{ | |
Console.WriteLine(reverseMerge(Console.ReadLine())); | |
} | |
/* | |
* Failed test case: | |
* bdabaceadaedaaaeaecdeadababdbeaeeacacaba | |
* output: | |
* aaaaaabaaceededecbdb | |
*/ | |
public static string reverseMerge(string s) | |
{ | |
if (!canBeReverseMerged(s)) | |
return ""; | |
int len = s.Length; | |
int half = len / 2; | |
string minOrder = ""; | |
bool foundFirstOne = false; | |
int[] A = getCountArray(s); | |
for (int i = 0; i + half < len; i++) | |
{ | |
string current = s.Substring(i, half); | |
int[] B = getCountArray(current); | |
if (isHalf(B, A)) | |
{ | |
if (!foundFirstOne) | |
{ | |
minOrder = current; | |
foundFirstOne = true; | |
} | |
else | |
minOrder = smallOne(current, minOrder); | |
} | |
} | |
return reverse(minOrder); | |
} | |
private static bool isHalf(int[] B, int[] A) | |
{ | |
for(int i=0;i<26;i++) | |
{ | |
if (B[i] * 2 == A[i]) | |
continue; | |
else | |
return false; | |
} | |
return true; | |
} | |
// assume both string have same length | |
// because it is reverse string | |
private static string smallOne(string tmpS1, string tmpS2) | |
{ | |
string s1 = reverse(tmpS1); | |
string s2 = reverse(tmpS2); | |
int len = s1.Length; | |
for(int i=0;i<len;i++) | |
{ | |
if (s1[i] < s2[i]) | |
return tmpS1; | |
else if (s1[i] > s2[i]) | |
return tmpS2; | |
} | |
// both are the same, any one | |
return tmpS1; | |
} | |
private static string reverse(string s) | |
{ | |
StringBuilder newS = new StringBuilder(); | |
for (int i = s.Length - 1; i >= 0; i--) | |
newS.Append(s[i].ToString()); | |
return newS.ToString(); | |
} | |
private static bool canBeReverseMerged(string s) | |
{ | |
if (s == null || s.Length == 0) return true; | |
int[] A = new int[26]; | |
for(int i=0; i < s.Length;i++) | |
{ | |
A[s[i]-'a']++; | |
} | |
for(int i=0;i<26;i++) | |
{ | |
if (A[i] % 2 == 1) | |
return false; | |
} | |
return true; | |
} | |
private static int[] getCountArray(string s) | |
{ | |
int[] A = new int[26]; | |
if (s == null || s.Length == 0) return A; | |
for (int i = 0; i < s.Length; i++) | |
{ | |
A[s[i] - 'a']++; | |
} | |
return A; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment