Created
April 27, 2016 18:33
-
-
Save jianminchen/b8263048c297473319c23836e9468c14 to your computer and use it in GitHub Desktop.
Bear and Gene Linear Search - C# code, modify variable name to make more meaningful, matching the design, support blog:http://juliachencoding.blogspot.ca/2016/03/hackerrank-bear-steady-gene-ii.html
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.IO; | |
class Solution | |
{ | |
public static int LEN = 4; | |
public static string GENES = "ACGT"; | |
static void Main(String[] args) | |
{ | |
int N = Int32.Parse(Console.ReadLine()); | |
string line = Console.ReadLine(); | |
Console.WriteLine(getMinimumSubstring(N, line)); | |
} | |
public static int getMinimumSubstring(int N, string line) | |
{ | |
int[] asciiTable = new int[256]; // 256 | |
for (int i = 0; i < N; i++) | |
{ | |
asciiTable[line[i]]++; | |
} | |
int[] searchStrArray = new int[4]; | |
for (int i = 0; i < 4; i++) | |
{ | |
searchStrArray[i] = asciiTable[GENES[i]] - N / 4; | |
} | |
int min = int.MaxValue; | |
if (allZero(searchStrArray)) | |
min = 0; | |
else | |
{ | |
min = N; // maximum value is N | |
int best = sumPositiveValue(searchStrArray); | |
int start = 0; | |
int end = 0; | |
// edge case - GAAATAAA | |
// G - one char in the substring | |
recountRightPtrMove(searchStrArray, line[start]); | |
while (min != best && start < N && end < N) | |
{ | |
if (foundOne(searchStrArray)) | |
{ | |
if (end - start + 1 < min) | |
min = end - start + 1; | |
// move start to next position | |
recountLeftPtrMove(searchStrArray, line[start]); | |
start++; | |
} | |
else | |
{ | |
end++; | |
if (end != N) // edge case | |
{ | |
recountRightPtrMove(searchStrArray, line[end]); | |
} | |
} | |
} | |
} | |
return min; | |
} | |
private static bool allZero(int[] cB) | |
{ | |
for (int i = 0; i < LEN; i++) | |
{ | |
if (cB[i] != 0) | |
return false; | |
} | |
return true; | |
} | |
private static int sumPositiveValue(int[] cB) | |
{ | |
int sum = 0; | |
for (int i = 0; i < LEN; i++) | |
{ | |
if (cB[i] > 0) | |
sum += cB[i]; | |
} | |
return sum; | |
} | |
/* | |
* check the array - each of them is less than 1. | |
* | |
*/ | |
private static bool foundOne(int[] arr) | |
{ | |
for (int i = 0; i < LEN; i++) | |
{ | |
if (arr[i] >= 1) | |
return false; | |
} | |
return true; | |
} | |
/* | |
* GAAATAAA | |
* G is removed from the substring, | |
* and then, | |
* Int array - arr needs to add one more for G | |
*/ | |
public static void recountLeftPtrMove(int[] arr, char chr) | |
{ | |
for (int i = 0; i < GENES.Length; i++) | |
{ | |
if (GENES[i] == chr) // meaningful name for global variable, code -> GENES - April 27, 2016 | |
arr[i]++; | |
} | |
} | |
/* | |
* GAAATAAA | |
* | |
* substring AAATA | |
* AATA, now another A is add to substring | |
* | |
* Int array - arr needs to add one more for G | |
*/ | |
public static void recountRightPtrMove(int[] arr, char chr) | |
{ | |
for (int i = 0; i < GENES.Length; i++) | |
{ | |
if (GENES[i] == chr) | |
arr[i]--; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment