# Determining DNA Health HackerRank Solution in C, C++, Java, Python

DNA is a nucleic acid present in the bodies of living things. Each piece of DNA contains a number of genes, some of which are beneficial and increase the DNA’s total health. Each gene has a health value, and the total health of a DNA is the sum of the health values of all the beneficial genes that occur as a substring in the DNA. We represent genes and DNA as non-empty strings of lowercase English alphabetic letters, and the same gene may appear multiple times as a susbtring of a DNA.

Given the following:

• An array of beneficial gene strings, genes = [g0,g1,g2…,gn-1]. Note that these gene sequences are not guaranteed to be distinct.
• An array of gene health values,health=[h0,h1,h2…,hn-1] , where each  is the health value for gene .
• A set of s DNA strands where the definition of each strand has three components,start ,end , and d, where string  is a DNA for which genes gstart,…,gend are healthy.

Find and print the respective total healths of the unhealthiest (minimum total health) and healthiest (maximum total health) strands of DNA as two space-separated values on a single line.

Constraints

• 1<=n, s<=10^5
• 0<=h<=10^7
• 0<=first<=last<n
• 1 <= the sum of the lengths of all genes and DNA strands <= 2*10^6
• It is guaranteed that each  consists of lowercase English alphabetic letters only (i.e., a to z).

Output Format

Print two space-separated integers describing the respective total health of the unhealthiest and the healthiest strands of DNA.

Sample Input 0

```6

a b c aa d b

1 2 3 4 5 6

3

1 5 caaab

0 4 xyz

2 4 bcdybc```

Sample Output 0

`0 19`

## Determining DNA Health HackerRank Solution in 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;
}```

## Determining DNA Health HackerRank Solution in Java

```import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class QuickScanner {
static final int BUFFER_NOT_READ = -1;
static final int BUFFER_SIZE = 64*1024;
final InputStream is;
int length;
byte[] buffer = new byte[BUFFER_SIZE];
QuickScanner(InputStream is) {
this.is = is;
}

throw new IllegalStateException(
"End of stream reached.");
}
curr = 0;
}

if (curr == BUFFER_NOT_READ || curr >= BUFFER_SIZE) {
}
}

char nextChar() throws IOException {
if (curr >= length) {
return ' ';
}
return (char) buffer[curr++];
}

// Currently only positive numbers are supported.
long nextLong() throws IOException {
StringBuilder sb = new StringBuilder();
while (true) {
char ch = nextChar();
if (ch >= '0' && ch <= '9') {
sb.append(ch);
} else {
break;
}
}
return Long.parseLong(sb.toString());
}

// Currently only positive numbers are supported.
int nextInt() throws IOException {
long l = nextLong();
assert(l < (long) Integer.MAX_VALUE);
return (int) l;
}

String nextAlphanumericString() throws IOException {
StringBuilder sb = new StringBuilder(256);
while (true) {
char ch = nextChar();
if ((ch >= 'a' && ch <= 'z') ||
(ch >= '0' && ch <= '9')) {
sb.append(ch);
} else {
break;
}
}
return sb.toString();
}

void close() throws IOException {
length = 0;
curr = 0;
is.close();
}
}

final int gene;
final int dna;
final boolean isStart;

DNATask(int gene, int dna, boolean isStart) {
this.gene = gene;
this.dna = dna;
this.isStart = isStart;
}

@Override
int comp;
comp = Integer.compare(gene, o.gene);
if (comp != 0) return comp;
comp = Integer.compare(dna, o.dna);
if (comp != 0) return comp;
return - Boolean.compare(isStart, o.isStart);
}

@Override
public String toString() {
"gene=" + gene +
", dna=" + dna +
", isStart=" + isStart +
'}';
}
}

class Node {
final Node parent;
final int ch;  // 0-25 : 'a' - 'z'
String nodeName;  // used only for printing the tree

Node[] children;
long score;

Node postfix;
Set<Node> reversePostfixes;

Node(Node parent, int ch) {
this.parent = parent;
this.ch = ch;
}

void add(String str, int strIdx, int sc) {
if (strIdx >= str.length()) {
score += sc;
// clearTotalScore();
} else {
int c = str.charAt(strIdx) - 'a';
if (children == null) {
children = new Node[26];
}
Node child = children[c];
if (child == null) {
children[c] = child = new Node(this, c);
child.calculatePostfix();
child.updateReversePostfixes(this);
}
}
}

void setPostfix(Node newPostfixNode) {
if (postfix != null) {
postfix.reversePostfixes.remove(this);
}
postfix = newPostfixNode;
if (newPostfixNode != null) {
Set<Node> h = newPostfixNode.reversePostfixes;
if (h == null) {
newPostfixNode.reversePostfixes =
h = new HashSet<>(4);
}
}
}

void calculatePostfix() {
if (parent == null) {
return;
}
Node p = parent.postfix;
if (p == null) {
setPostfix(parent);
return;
}
while (true) {
if (p.children != null) {
Node child = p.children[ch];
if (child != null) {
setPostfix(child);
break;
}
}
if (p.postfix == null) {
setPostfix(p);
break;
}
p = p.postfix;
}
}

void updateReversePostfixes(Node parentNode) {
if (parentNode == null || parentNode == this ||
parentNode.reversePostfixes == null) return;
for (Node n:parentNode.reversePostfixes.toArray(
new Node[0])) {
if (n.children != null) {
Node sameChild = n.children[ch];
if (sameChild != null) {
sameChild.setPostfix(this);
continue;
}
}
updateReversePostfixes(n);
}
}

String getNodeName() {
if (nodeName == null) {
nodeName = parent == null
? "l_" : parent.getNodeName() + (char)(ch + 'a');
}
return nodeName;
}

@Override
public String toString() {
return "Node{" +
"ch=" + (char)(ch + 'a') +
", nodeName='" + getNodeName() + '\'' +
", score=" + score +
", postfix=" + (postfix == null ?
'-' : postfix.getNodeName()) +
'}';
}

void printTree() {
System.err.println(getNodeName() +
" [ label=\"" + (char)(ch + 'a') +
": " + score + " (" + getTotalScore() + ")\" ]");
if (parent != null) {
System.err.println(
parent.getNodeName() + " -> " + getNodeName());
}
if (postfix != null) {
System.err.println(
getNodeName() + " -> " +
postfix.getNodeName() + " [color=blue]");
}
if (children != null) {
for (int i = 0; i < 26; i++) {
Node child = children[i];
if (child != null) child.printTree();
}
}
}

public long getTotalScore() {
long sc = score;
if (postfix != null) {
sc += postfix.getTotalScore();
}
return sc;
}
}

class DNAHealth {
private static final int SPACE = ' ' - 'a';

int n;  // number of genes
String[] genes;
int[] scores;

int s;  // number of DNA strands
String[] dnaStrands;
long[] dnaScores;

long startTime;
long lastTime;

void startTimer() {
startTime = System.nanoTime();
lastTime = startTime;
System.err.println("--- Timer started.");
}

synchronized void logTime(String txt) {
long now = System.nanoTime();
System.err.format("--- %8.3fms (%8.3fms) %s\n",
(now - startTime)/1000000.0, (now - lastTime)/1000000.0, txt);
lastTime = now;
}

long walkTime = 0;
long walkCount = 0;

void readInitialData(String inputFile) throws IOException {
final QuickScanner scanner = new QuickScanner(inputFile == null ? System.in : new FileInputStream(inputFile));
n = scanner.nextInt();

genes = new String[n];

for (int i = 0; i < n; i++) {
genes[i] = scanner.nextAlphanumericString();
}

scores = new int[n];

for (int i = 0; i < n; i++) {
scores[i] = scanner.nextInt();
}

s = scanner.nextInt();

dnaStrands = new String[s];
for (int i = 0; i < s; i++) {
int first = scanner.nextInt();
int last = scanner.nextInt();
dnaStrands[i] = scanner.nextAlphanumericString();
int idx = 2*i;
}
scanner.close();
dnaScores = new long[s];
logTime("DNA Strands read: " + s);
}

final int partition;
final int geneStart;
int geneEnd;
Integer[] finishProc;
long t0;

void resetT0() {
t0 = System.nanoTime();
}

void endWalkTime() {
synchronized (DNAHealth.this) {
walkTime += System.nanoTime() - t0;
walkCount++;
}
}

synchronized (DNAHealth.this) {
}
}

super("Partition " + partition);
this.partition = partition;
this.geneStart = geneStart;
}

@Override
public void run() {
partition + " started. geneStart: " + geneStart);
final Node tree = new Node(null, SPACE);
int treeBuiltIdx = geneStart - 1;
while (treeBuiltIdx < task.gene - 1) {
treeBuiltIdx++;
resetT0();
}
long score = (task.isStart ? -1L : 1L)
synchronized (DNAHealth.this) {
}
}
while (treeBuiltIdx < geneEnd - 1) {
treeBuiltIdx++;
resetT0();
}
for (int finishProcDna : finishProc) {
long sc = calcScoreForStrand(tree, dnaStrands[finishProcDna]);
synchronized (DNAHealth.this) {
dnaScores[finishProcDna] += sc;
}
}
logTime("Thread for partition " + partition + " completed.");
}

long calcScoreForStrand(Node tree, String d) {
resetT0();
Node p = tree;
long score = 0;
for (int i = 0; i < d.length(); i++) {
int c = d.charAt(i) - 'a';
while (true) {
if (p.children != null) {
Node child = p.children[c];
if (child != null) {
p = child;
score += p.getTotalScore();
break;
}
}
if (p.postfix == null) {
// we are at root.
break;
}
p = p.postfix;
}
}
endWalkTime();
return score;
}
}

void calcStrands() throws Exception {
int partitions =
n > 50 * s ? 8 :
n > 5 * s ? 4 : 1;
logTime("Partitions: " + partitions);
if (partitions > n) partitions = n;
Set<Integer> dnasInProgress = new HashSet<>();
int lastPartition = -1;
for (int i = 0; i < dnaTasks.length; i++) {
int partition = (int) (
(task.gene - 1.0) * partitions / (n + 0.0) );
if (partition != lastPartition) {
if (lastPartition >= 0) {
dnasInProgress.toArray(new Integer[0]);
}
lastPartition = partition;
}

}

} else {
}
}
if (lastPartition >= 0 && threads[lastPartition] != null) {
}
}
}

void printTree(int builtUpTo) {
System.err.println("*** Tree built up to " + (builtUpTo - 1));
System.err.println("digraph x {");
// tree.printTree();
System.err.println("}");
}

void run(String[] args) throws Exception {
startTimer();
readInitialData(args.length > 0 ? args[0] : null);
calcStrands();
logTime("Calculated.");
long minScore = Long.MAX_VALUE;
long maxScore = Long.MIN_VALUE;
for (int i = 0; i < s; i++) {
long score = dnaScores[i];
if (score > maxScore) {
maxScore = score;
}
if (score < minScore) {
minScore = score;
}
}
logTime(String.format(
"End. Add time (%d): %8.3fms, Walk time (%d): %8.3fms",
walkCount, walkTime / 1000000.0));
System.out.println(minScore + " " + maxScore);
}
}

public class Solution {
public static void main(String[] args) throws Exception {
new DNAHealth().run(args);
}
}
```

## Determining DNA Health HackerRank Solution in 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

# ------------------------------------------------------------------------------
howGenes = int(input())
genes = input().rstrip().split()
healths = list(map(int, input().rstrip().split()))
howStrands = int(input())
gMap = defaultdict(lambda: [[], [0]])
subs = set()
for id, gene in enumerate(genes):
gMap[gene][0].append(id)
for j in range(1, min(len(gene), 500)+1): subs.add(gene[:j])
for v in gMap.values():
for i, ix in enumerate(v[0]): v[1].append(v[1][i]+healths[ix])

# ------------------------------------------------------------------------------
largest = max(list(map(len, genes)))
hMin, hMax = inf, 0
for _ in range(howStrands):
firstLastd = input().split()
first = int(firstLastd[0])
last = int(firstLastd[1])
strand = firstLastd[2]
h = getHealth(strand, first, last, largest)
hMin, hMax = min(hMin, h), max(hMax, h)
print(hMin, hMax)```

## Determining DNA Health HackerRank Solution in C#

```using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
static void Main(String[] args)
{
int[] values = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
var trie = MakeTrie(patterns, values);
ulong max = ulong.MinValue;
ulong min = ulong.MaxValue;
for (int a = 0; a < s; a++)
{
if (str == null)
continue;
string[] tokens = str.Split(' ');
int first = Convert.ToInt32(tokens[0]);
int last = Convert.ToInt32(tokens[1]);
string d = tokens[2];
ulong val = GetValue(trie, d, first, last);
if (val > max) max = val;
if (val < min) min = val;
}

Console.WriteLine("{0} {1}", min, max);
}

private static Trie MakeTrie(string[] patterns, int[] values)
{
var trie = new Trie();
int index = 0;
foreach (var item in patterns)
{
}

return trie;
}

private static ulong GetValue(Trie t, string d, int first, int last)
{
Node runner;
ulong total = 0;
var index = new List<int>();
var value = new List<int>();
bool isEndOfWord = false;
for (int i = 0; i < d.Length; ++i)
{
isEndOfWord = false;
for (int j = 0; j + i < d.Length; ++j)
{
runner = t.FindNextLetter(d[i + j], ref isEndOfWord, ref index, ref value, runner);
if (runner == null) break;
if (isEndOfWord)
{
isEndOfWord = false;
for (int k = 0; k < index.Count; k++)
{
if (index[k] >= first && index[k] <= last)
total += (ulong)value[k];
}
}

}
}

}

}

public class Trie
{
public Trie()
{
}

{
}

public void AddWord(string word, int index, int value)
{
for(int i = 0; i < word.Length; ++i)
{
}

runner.SetIsEndOfWord();
runner.SetIndex(index);
runner.SetValue(value);
}

public Node FindNextLetter(char letter, ref bool IsEndOfWord, ref List<int> Index, ref List<int> Value, Node node)
{
if (node == null) return null;
Node curr = node.GetLetter(letter);
if (curr == null) return null;
if (curr.IsEndOfWord)
{
Index = curr.Index;
Value = curr.Value;
IsEndOfWord = true;
}

return curr;
}
}

public class Node
{
Node[] letters;

public Node(char c)
{
CurrentChar = c;
if(letters == null)
letters = new Node[26];
}

public Node()
{
CurrentChar = null;
if (letters == null)
letters = new Node[26];
}

public List<int> Index { get; private set; }
public bool IsEndOfWord { get; private set; }
public char? CurrentChar { get; private set; }
public List<int> Value { get; private set; }

{
if (letters[c - 'a'] == null)
{
letters[c - 'a'] = new Node(c);
}

return letters[c - 'a'];
}

public Node GetLetter(char c)
{
return letters[c - 'a'];
}

public void SetIndex(int i)
{
if (Index == null) Index = new List<int>();
}

public void SetValue(int i)
{
if (Value == null) Value = new List<int>();