Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created March 6, 2016 01:49
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/61dfe437f82edb9793fc to your computer and use it in GitHub Desktop.
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.
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