Created
March 6, 2016 01:49
-
-
Save jianminchen/61dfe437f82edb9793fc to your computer and use it in GitHub Desktop.
Bear And Steady Gene - algorithm using two pointers - O(N) solution in time complexity.
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 code = "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[] cA = new int[256]; // 256 | |
for (int i = 0; i < N; i++ ) | |
{ | |
cA[line[i]]++; | |
} | |
int[] cB = new int[4]; | |
for (int i = 0; i < 4; i++ ) | |
{ | |
cB[i] = cA[code[i]] - N / 4; | |
} | |
int min = int.MaxValue; | |
if (allZero(cB)) | |
min = 0; | |
else | |
{ | |
min = N; // maximum value is N | |
int best = sumPositiveValue(cB); | |
int start = 0; | |
int end = 0; | |
// edge case - GAAATAAA | |
// G - one char in the substring | |
updateCBAdd(cB, line[start]); | |
while (min != best && start < N && end < N) | |
{ | |
if (cBAllLessThan1(cB)) | |
{ | |
if (end - start + 1 < min) | |
min = end - start + 1; | |
// move start to next position | |
updateCBRemove(cB, line[start]); | |
start++; | |
} | |
else | |
{ | |
end++; | |
if(end != N) // edge case | |
{ | |
updateCBAdd(cB, 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; | |
} | |
private static bool cBAllLessThan1(int[] cB) | |
{ | |
for(int i=0; i< LEN; i++) | |
{ | |
if(cB[i] >= 1) | |
return false; | |
} | |
return true; | |
} | |
/* | |
* GAAATAAA | |
* G is removed from the substring, | |
* and then, | |
* cB needs to add one more for G | |
*/ | |
public static void updateCBRemove(int[] cB, char chr) | |
{ | |
for(int i=0;i<code.Length;i++) | |
{ | |
if(code[i] == chr) // bug002 - not CB[i], should be code[i] | |
cB[i] ++; | |
} | |
} | |
/* | |
* GAAATAAA | |
* | |
* substring AAATA | |
* AATA, now another A is add to substring | |
* | |
* cB needs to add one more for G | |
*/ | |
public static void updateCBAdd(int[] cB, char chr) | |
{ | |
for (int i = 0; i < code.Length; i++) | |
{ | |
if (code[i] == chr) // bug 001 - code[i], not cB[i], two arrays are mixed! | |
cB[i]--; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment