Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created March 6, 2016 06:21
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save jianminchen/0892107fc0f6b6bec7a0 to your computer and use it in GitHub Desktop.
Save jianminchen/0892107fc0f6b6bec7a0 to your computer and use it in GitHub Desktop.
Bear And Steady Gene algorithm - two pointer solution, linear solution
using System;
using System.Collections.Generic;
using System.IO;
class Solution
{
/*
* Julia write the C# code,
* code source: Java code
* https://gist.github.com/jianminchen/d52ced38de0bffa2d9e8
*/
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 s)
{
int mx = n / 4;
int[] cnt = new int[256];
foreach (char c in s) {
cnt[c]++;
}
string t = "ACGT";
bool ok = true;
foreach (char c in t) {
if (cnt[c] > mx) {
ok = false;
}
}
if (ok)
return 0;
int r = 0;
int ans = n;
for (int l= 0; l < n; l++) {
while (cnt['A'] > mx || cnt['C'] > mx || cnt['T'] > mx || cnt['G'] > mx) {
if (r == n) {
return ans;
}
--cnt[s[r]];
++r;
}
ans = Math.Min(ans, r - l);
++cnt[s[l]];
}
return ans;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment