Determining DNA Health – HackerRank Solution

In this post, we will solve Determining DNA Health HackerRank Solution. This problem (Determining DNA Health) is a part of HackerRank Problem Solving series.

Solution – Determining DNA Health – HackerRank Solution

C++

```#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>
#include <cmath>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <cstdlib>

using namespace std;

#define INF 1e+9
#define mp make_pair
#define pb push_back
#define fi first
#define fs first
#define se second
#define i64 long long
#define li long long
#define lint long long
#define pii pair<int, int>
#define vi vector<int>

#define forn(i, n) for (int i = 0; i < (int)n; i++)
#define fore(i, b, e) for (int i = (int)b; i <= (int)e; i++)

struct vertex {
int next[26];
vi numbers;
int p;
char pch;
int go[26];
};

const int maxn = 2e6+5;

vertex t[maxn];
int sz;
int cost[maxn];

void init() {
memset (t[0].next, 255, sizeof t[0].next);
memset (t[0].go, 255, sizeof t[0].go);
sz = 1;
}

void add_string (const string & s, int num) {
int v = 0;
for (size_t i=0; i<s.length(); ++i) {
int c = s[i]-'a';
if (t[v].next[c] == -1) {
memset (t[sz].next, 255, sizeof t[sz].next);
memset (t[sz].go, 255, sizeof t[sz].go);
t[sz].p = v;
t[sz].pch = c;
t[v].next[c] = sz++;
}
v = t[v].next[c];
}
t[v].numbers.pb(num);
}

int go (int v, int c);

if (v == 0 || t[v].p == 0)
else
}
}

int go (int v, int c) {
if (t[v].go[c] == -1) {
if (t[v].next[c] != -1)
t[v].go[c] = t[v].next[c];
else
t[v].go[c] = v==0 ? 0 : go (get_link (v), c);
}
return t[v].go[c];
}

int main() {
#ifdef LOCAL
freopen("inp", "r", stdin);
//freopen("outp", "w", stdout);
#else
#endif
init();
int n;
scanf("%d", &n);
forn(j, n) {
string s;
cin >> s;
//        cout << "s = " << s << endl;
}
forn(j, n)
scanf("%d", &cost[j]);
int q;
scanf("%d", &q);
i64 minn = 0;
i64 maxx = 0;
forn(query, q) {
int L, R;
scanf("%d%d", &L, &R);
string s;
cin >> s;
int cur = 0;
i64 sum = 0;
for (char c : s) {
cur = go(cur, (int)(c - 'a'));
//printf("cur = %d\n", cur);
int tmp = cur;
while(tmp != 0) {
for (int x : t[tmp].numbers) {
if (x >= L && x <= R)
sum += cost[x];
//printf("%c x = %d sum = %lld\n", c, x, sum);
}
}
}
if (query == 0 || sum > maxx)
maxx = sum;
if (query == 0 || sum < minn)
minn = sum;
}
cout << minn << " " << maxx;
}
```

Python

```from math import inf
from bisect import bisect_left as bLeft, bisect_right as bRight
from collections import defaultdict

def getHealth(seq, first, last, largest):
h, ls = 0, len(seq)

for f in range(ls):
for j in range(1, largest+1):
if f+j > ls:
break
sub = seq[f:f+j]
if sub not in subs:
break
if sub not in gMap:
continue
ids, hs = gMap[sub]
h += hs[bRight(ids, last)]-hs[bLeft(ids, first)]
return h

if __name__ == '__main__':

n = int(input())
genes = input().rstrip().split()
health = list(map(int, input().rstrip().split()))

gMap = defaultdict(lambda: [[], [0]])
subs = set()
for i, gene in enumerate(genes):
gMap[gene][0].append(i)
for j in range(1, min(len(gene), 500)+1):

for v in gMap.values():
for i, ix in enumerate(v[0]):
v[1].append(v[1][i]+health[ix])

largest = max(list(map(len, genes)))
hMin, hMax = inf, 0

s = int(input())
for s_itr in range(s):
firstLastd = input().split()
first = int(firstLastd[0])
last = int(firstLastd[1])
d = firstLastd[2]
h = getHealth(d, first, last, largest)
hMin, hMax = min(hMin, h), max(hMax, h)

print(hMin, hMax)
```

Java

```import java.io.BufferedReader;
import java.io.File;
import java.io.PrintStream;
import java.util.Arrays;

public class Solution {

private static String[] genes;
private static int[] health;

public static void main(String[] args) throws Exception {
PrintStream out = new PrintStream(System.out);

long startMillis = System.currentTimeMillis();

genes = new String[n];
int longestKey = 0;

Trie trie = new Solution().new Trie();
for (int i = 0; i < n; i++) {
String genesItem = genesItems[i];
genes[i] = genesItem;

trie.insert(genes[i], i);

if (genes[i].length() > longestKey)
longestKey = genes[i].length();
}

health = new int[n];

for (int i = 0; i < n; i++) {
int healthItem = Integer.parseInt(healthItems[i]);
health[i] = healthItem;
}

//out.println("Longest key: " + longestKey);
startMillis = System.currentTimeMillis();

long maxH = 0, minH = Long.MAX_VALUE;

for (int sItr = 0; sItr < s; sItr++) {

int first = Integer.parseInt(firstLastd[0]);
int last = Integer.parseInt(firstLastd[1]);

String d = firstLastd[2];
long total = 0;
int keyLen = d.length();

for (int i = 0; i < keyLen; i++) {
total += trie.find(d.substring(i, keyLen > longestKey && i + longestKey < keyLen? i + longestKey : keyLen), first, last);
}

if (total > maxH)
maxH = total;

if (total < minH)
minH = total;
}

in.close();
out.println(minH + " " + maxH);
out.close();
}

class Trie {
private final short SIZE = 26;
private TrieNode root;

public Trie () {
this.root = new TrieNode();
}

class TrieNode {
private TrieNode[] children = new TrieNode[SIZE];
private int index[];
private boolean isEnd;

public TrieNode(){
isEnd = false;
}

@Override
public String toString(){
return (index != null? Arrays.toString(index) + " " : "")
+ Arrays.toString(Arrays.stream(children).filter(p -> p != null).toArray());
}
}

public void insert(String key, int index) {
int arrayPos;

TrieNode node = root;

for (int i = 0; i < key.length(); i++) {
arrayPos = key.charAt(i) - 'a';

if (node.children[arrayPos] == null) {
node.children[arrayPos] = new TrieNode();
}

node = node.children[arrayPos];
}

if (node.index == null) {
node.index = new int[1];
} else {
node.index = Arrays.copyOf(node.index, node.index.length + 1);
}

node.index[node.index.length - 1] = index;
node.isEnd = true;
}

public long find(String key, int start, int end) {
int arrayPos;

TrieNode node = root;
long result = 0;
int keyLen = key.length();

for (int i = 0; i < keyLen; i++) {
arrayPos = key.charAt(i) - 'a';

if (node.children[arrayPos] != null) {
node = node.children[arrayPos];

if (node.isEnd
&& (   start <= node.index[node.index.length - 1]
|| end >= node.index[0])) {

int sI = -1, eI = -1;
for (int j = 0, k = node.index.length - 1; j < node.index.length && k >= 0; j++, k--) {
if (sI == -1) {
if (node.index[j] >= start)
sI = j;
else if (node.index[k] < start && k + 1 < node.index.length && node.index[k + 1] >= start)
sI = k + 1;
}

if (eI == -1) {
if (node.index[k] <= end)
eI = k;
else if (node.index[j] > end && j - 1 >= 0 && node.index[j - 1] <= end)
eI = j - 1;
}

if (j == k || (sI != -1 && eI != -1))
break;
}

if (sI != -1 && eI != -1) {
for (int j = sI; j <= eI; j++) {
result += health[node.index[j]];
}
}
}
} else
break;
}

return result;
}

@Override
public String toString() {
return root.toString();
}
}
}
```

Note: This problem (Determining DNA Health) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.