Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created April 14, 2016 05:32
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/9b02beab326b2bfcd4b524f219d2946f to your computer and use it in GitHub Desktop.
Save jianminchen/9b02beab326b2bfcd4b524f219d2946f to your computer and use it in GitHub Desktop.
Bear and Steady Gene - add comment to explain the for loop - sliding window design
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;
* */
return getMinimumLength(cnt, n, mx, s);
}
/*
* sliding window:
* start pointer: l
* end pointer: r
*
* For example:
* GAAATAAA
*
* windows l=0, r=0, size of window is 0;
*
* First, loop on start pointer l,
* when l = 0, keep the start pointer as is, move end pointer until the rest of string
* satisfies condition: any char in "ACGT"'s count <= mx, for test case GAAATAAA, mx =2
*
* r = 6, exit while loop inside for loop
* sliding windows is l=0, r=6.
* In other words, string "GAAATA" is one of strings.
*
* Then, sliding window's start pointer l increases to next value 1, and then, repeat the process.
* "AAATA" is also one of strings, but length is shorter than "GAAATA".
*/
private static int getMinimumLength(int[] cnt, int n, int mx, string s)
{
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