forked from charles-wangkai/codility
-
Notifications
You must be signed in to change notification settings - Fork 0
/
GenomicRangeQuery.java
37 lines (33 loc) · 992 Bytes
/
GenomicRangeQuery.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.HashMap;
import java.util.Map;
public class GenomicRangeQuery {
public int[] solution(String S, int[] P, int[] Q) {
Map<Character, int[]> letter2counts = new HashMap<Character, int[]>();
char[] letters = { 'A', 'C', 'G', 'T' };
for (char letter : letters) {
letter2counts.put(letter, buildCounts(S, letter));
}
int[] minImpacts = new int[P.length];
for (int i = 0; i < P.length; i++) {
for (int j = 0; j < letters.length; j++) {
if (countIn(letter2counts.get(letters[j]), P[i], Q[i]) > 0) {
minImpacts[i] = j + 1;
break;
}
}
}
return minImpacts;
}
int[] buildCounts(String S, char letter) {
int[] counts = new int[S.length()];
for (int i = 0; i < counts.length; i++) {
counts[i] = (i == 0 ? 0 : counts[i - 1])
+ (S.charAt(i) == letter ? 1 : 0);
}
return counts;
}
int countIn(int[] counts, int beginIndex, int endIndex) {
return counts[endIndex]
- (beginIndex == 0 ? 0 : counts[beginIndex - 1]);
}
}