Created
April 27, 2016 20:57
-
-
Save jianminchen/b23c4f606a101b9aeec71eff3268db32 to your computer and use it in GitHub Desktop.
Bear And Gene - Linear search - more update on meaningful names
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[] searchStrNumbers = new int[4]; | |
for (int i = 0; i < 4; i++) | |
{ | |
searchStrNumbers[i] = asciiTable[GENES[i]] - N / 4; | |
} | |
int min = int.MaxValue; | |
if (allZero(searchStrNumbers)) | |
min = 0; | |
else | |
{ | |
min = N; // maximum value is N | |
int best = sumPositiveValue(searchStrNumbers); | |
int start = 0; | |
int end = 0; | |
// edge case - GAAATAAA | |
// G - one char in the substring | |
recountRightPtrMove(searchStrNumbers, line[start]); | |
while (min != best && start < N && end < N) | |
{ | |
if (foundOne(searchStrNumbers)) | |
{ | |
if (end - start + 1 < min) | |
min = end - start + 1; | |
// move start to next position | |
recountLeftPtrMove(searchStrNumbers, line[start]); | |
start++; | |
} | |
else | |
{ | |
end++; | |
if (end != N) // edge case | |
{ | |
recountRightPtrMove(searchStrNumbers, line[end]); | |
} | |
} | |
} | |
} | |
return min; | |
} | |
private static bool allZero(int[] arr) | |
{ | |
for (int i = 0; i < LEN; i++) | |
{ | |
if (arr[i] != 0) | |
return false; | |
} | |
return true; | |
} | |
private static int sumPositiveValue(int[] arr) | |
{ | |
int sum = 0; | |
for (int i = 0; i < LEN; i++) | |
{ | |
if (arr[i] > 0) | |
sum += arr[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