Created
April 14, 2016 05:32
-
-
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
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 | |
{ | |
/* | |
* 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