Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Last active April 2, 2016 22:03
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/37e3c65f03f62dcdeb2e9634a11e0efa to your computer and use it in GitHub Desktop.
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
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