Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created April 27, 2016 20:57
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/b23c4f606a101b9aeec71eff3268db32 to your computer and use it in GitHub Desktop.
Save jianminchen/b23c4f606a101b9aeec71eff3268db32 to your computer and use it in GitHub Desktop.
Bear And Gene - Linear search - more update on meaningful names
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