Hackerrank Determining DNA Health problem solution

Hackerrank Determining DNA Health problem solution – 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.
• An array of gene health values.
• A set of  DNA strands where the definition of each strand has three component.

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.

Hackerrank Determining DNA Health problem 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 problem solution in Java.

import java.io.BufferedReader;
import java.io.File;
import java.io.InputStreamReader;
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();
        
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());

        genes = new String[n];
        int longestKey = 0;
        
        String[] genesItems = in.readLine().split(" ");

        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];

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

        //out.println("Longest key: " + longestKey);
        //out.println("Loading: " + (System.currentTimeMillis() - startMillis)/1000f);
        startMillis = System.currentTimeMillis();
        
        int s = Integer.parseInt(in.readLine());
        long maxH = 0, minH = Long.MAX_VALUE;
        
        for (int sItr = 0; sItr < s; sItr++) {
            String[] firstLastd = in.readLine().split(" ");

            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();
        }
    }
}

Problem solution in C++ programming.

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


struct trie 
{
  vector<int> term;
  struct trie* next[26];
  struct trie* fail;
  trie() 
  {
    fail = NULL;
    for (int i=0; i<26; i++)
      next[i] = NULL;
  }
};
trie *root;

void insert(char str[], int index)
{
  trie* p = root;
  int len = strlen(str);
  for (int i=0; i<len; i++)
  {
    int idx = str[i]-'a';
    if (p->next[idx]==NULL)
      p->next[idx] = new trie();
    p = p->next[idx];
  }
  p->term.push_back(index);
}

void buildfail()
{
  queue<trie*> q;
  q.push(root);
  while(!q.empty())
  {
    trie* cur = q.front();
    q.pop();
    for (int i=0; i<26; i++)
    {
      if (cur->next[i] != NULL)
      {
        if (cur == root)
          cur->next[i]->fail = root;
        else
        {
          trie* p = cur->fail;
          while (p!=NULL && p->next[i] == NULL)
            p = p->fail;
          if (p==NULL)
            cur->next[i]->fail = root;
          else
            cur->next[i]->fail = p->next[i];
        }
        q.push(cur->next[i]);
      }
    }
  }
}


vector<pair<vector<int>, int> > query(char str[])
{
  vector<pair<vector<int>, int> > ret;
  int len = strlen(str);
  trie* p = root;
  for (int i=0; i<len; i++)
  {
    int idx = str[i] - 'a';
    while (p->next[idx] == NULL && p!=root)
      p = p->fail;
    if (p->next[idx] == NULL)
      continue;
    p = p->next[idx];
    trie* pp = p;
    while (pp != root)
    {
      if (!pp->term.empty())
        ret.push_back(make_pair(pp->term, i));
      pp = pp->fail;
    }
  }
  return ret;
}

int main()
{
  int n;
  int health[100000];
  char str[2000001];
  scanf("%d", &n);
  root = new trie();
  for (int i=0; i<n; i++)
  {
    scanf("%s", str);
    insert(str, i);
  }
  for (int i=0; i<n; i++)
    scanf("%d", &health[i]);
  buildfail();
  int q;
  scanf("%d", &q);
  long long mins=9999999999999,maxs=0;
  for (int i=0; i<q; i++)
  {
    int a,b;
    scanf("%d %d %s", &a, &b, str);
    vector<pair<vector<int>,int> > ret = query(str);
    long long sum = 0;
    for (int i=0; i<ret.size(); i++)
      for (int j=0; j<ret[i].first.size(); j++)
        if (ret[i].first[j] >= a && ret[i].first[j] <= b)
          sum += health[ret[i].first[j]];
    if (sum > maxs)
      maxs = sum;
    if (sum < mins)
      mins = sum;
  }
  printf("%lld %lldn", mins, maxs);
}

Problem solution in C programming.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* readline();
char** split_string(char*);

typedef struct TreeNode {
    char ch;
    int* ids;
    int idsLen;
    bool isBlue;
    struct TreeNode* child;
    struct TreeNode* next;
    struct TreeNode* suffix;
    struct TreeNode* blueSuffix;
} TreeNode;

TreeNode* initNode() {
    TreeNode* node = malloc(sizeof(TreeNode));
    node->ch = 0;
    node->ids = NULL;
    node->idsLen = 0;
    node->isBlue = false;
    node->child = NULL;
    node->next = NULL;
    node->suffix = NULL;
    node->blueSuffix = NULL;
    return node;
}

void fillSuffix(TreeNode* root, int size) {
    TreeNode** queue = malloc(size*sizeof(TreeNode*));
    queue[0] = root;
    int head = 0;
    int tail = 1;
    while (head<tail) {
        TreeNode* node = queue[head++];
        TreeNode* child = node->child;
        while (child != NULL) {
            TreeNode* parent_suf = node->suffix;
            bool found_suf = false;
            while (!found_suf && parent_suf != NULL) {
                TreeNode* parent_suf_child = parent_suf->child;
                while (parent_suf_child != NULL && parent_suf_child->ch != child->ch) {
                    parent_suf_child = parent_suf_child->next;
                }
                if (parent_suf_child != NULL) {
                    child->suffix = parent_suf_child;
                    found_suf = true;
                } else {
                    parent_suf = parent_suf->suffix;
                }
            }
            if (!found_suf) child->suffix = root;
            
            queue[tail++] = child;
            child = child->next;
        }
    }
    free(queue);
}

void fillBlueSuffix(TreeNode* root, int size) {
    TreeNode** queue = malloc(size*sizeof(TreeNode*));
    queue[0] = root;
    int head = 0;
    int tail = 1;
    while (head<tail) {
        TreeNode* node = queue[head++];
        TreeNode* child = node->child;
        while (child != NULL) {
            TreeNode* parent_suf = node->suffix;
            bool found_suf = false;
            while (!found_suf && parent_suf != NULL) {
                TreeNode* parent_suf_child = parent_suf->child;
                while (parent_suf_child != NULL && parent_suf_child->ch != child->ch) {
                    parent_suf_child = parent_suf_child->next;
                }
                if (parent_suf_child != NULL && parent_suf_child->isBlue) {
                    child->blueSuffix = parent_suf_child;
                    found_suf = true;
                } else {
                    parent_suf = parent_suf->suffix;
                }
            }
            if (!found_suf) child->blueSuffix = root;
            
            queue[tail++] = child;
            child = child->next;
        }
    }
    free(queue);
}

TreeNode* contructTree(char** genes, int genes_count) {
    TreeNode* root = initNode();
    int size=1;
    for (int i=0; i<genes_count; i++) {
        TreeNode* node = root;
        char* gen = genes[i];
        int len = strlen(gen);
        for (int j=0; j<len; j++) {
            TreeNode* child;
            if (node->child == NULL) {
                child = initNode();
                node->child = child;
                size++;
            } else {
                child = node->child;
                while (child->ch != gen[j] && child->next != NULL) child = child->next;
                if (child->ch != gen[j]) {
                    child->next = initNode();
                    child = child->next;
                    size++;
                }
            }
            node = child;
            node->ch = gen[j];
            if (j==len-1) {
                node->isBlue = true;
                if (node->idsLen == 0) {
                    node->ids = malloc(sizeof(int));
                } else {
                    node->ids = realloc(node->ids, (node->idsLen+1)*sizeof(int));
                }
                node->ids[node->idsLen] = i;
                node->idsLen++;
            }
        }
    }
    fillSuffix(root, size);
    fillBlueSuffix(root, size);
    return root;
}

TreeNode* getChildNode(TreeNode* node, char ch) {
    TreeNode* child = node->child;
    while (child != NULL && child->ch != ch) child = child->next;
    return child;
}

long calHealth(TreeNode* tree, int* health, int first, int last, char* d) {
    long result = 0;
    TreeNode* cur = tree;
    for (int i=0; i<strlen(d); i++) {
        TreeNode* child = getChildNode(cur, d[i]);
        while (child == NULL && cur->suffix != NULL) {
            cur = cur->suffix;
            child = getChildNode(cur, d[i]);
        }
        if (child != NULL) cur = child;
        TreeNode* blue_suffix = cur;
        while (blue_suffix != NULL) {
            for (int i=0; i<blue_suffix->idsLen; i++) {
                if (blue_suffix->ids[i]>=first && blue_suffix->ids[i]<=last) {
                    result += health[blue_suffix->ids[i]];
                }
            }
            blue_suffix = blue_suffix->blueSuffix;
        }
    }
    return result;
}

int main()
{
    char* n_endptr;
    char* n_str = readline();
    int n = strtol(n_str, &n_endptr, 10);
    if (n_endptr == n_str || *n_endptr != '') { exit(EXIT_FAILURE); }

    char** genes_temp = split_string(readline());
    char** genes = malloc(n * sizeof(char*));
    for (int i = 0; i < n; i++) {
        char* genes_item = *(genes_temp + i);
        *(genes + i) = genes_item;
    }
    
    TreeNode* tree = contructTree(genes, n);

    char** health_temp = split_string(readline());
    int* health = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        char* health_item_endptr;
        char* health_item_str = *(health_temp + i);
        int health_item = strtol(health_item_str, &health_item_endptr, 10);
        if (health_item_endptr == health_item_str || *health_item_endptr != '') { exit(EXIT_FAILURE); }
        *(health + i) = health_item;
    }

    char* s_endptr;
    char* s_str = readline();
    int s = strtol(s_str, &s_endptr, 10);
    if (s_endptr == s_str || *s_endptr != '') { exit(EXIT_FAILURE); }

    long* dna_healths = malloc(s*sizeof(long));

    for (int s_itr = 0; s_itr < s; s_itr++) {
        char** firstLastd = split_string(readline());

        char* first_endptr;
        char* first_str = firstLastd[0];
        int first = strtol(first_str, &first_endptr, 10);
        if (first_endptr == first_str || *first_endptr != '') { exit(EXIT_FAILURE); }

        char* last_endptr;
        char* last_str = firstLastd[1];
        int last = strtol(last_str, &last_endptr, 10);
        if (last_endptr == last_str || *last_endptr != '') { exit(EXIT_FAILURE); }

        char* d = firstLastd[2];
        dna_healths[s_itr] = calHealth(tree, health, first, last, d);
    }
    
    long minHealth = 1000000000000000000;
    long maxHealth = 0;
    for (int i=0; i<s; i++) {
        if (minHealth>dna_healths[i]) minHealth=dna_healths[i];
        if (maxHealth<dna_healths[i]) maxHealth=dna_healths[i];
    }
    printf("%ld %ld", minHealth, maxHealth);

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) { break; }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == 'n') { break; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == 'n') {
        data[data_length - 1] = '';
    }

    data = realloc(data, data_length);

    return data;
}

char** split_string(char* str) {
    char** splits = NULL;
    char* token = strtok(str, " ");

    int spaces = 0;

    while (token) {
        splits = realloc(splits, sizeof(char*) * ++spaces);
        if (!splits) {
            return splits;
        }

        splits[spaces - 1] = token;

        token = strtok(NULL, " ");
    }

    return splits;
}

Problem solution in JavaScript programming.

'use strict';

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.replace(/s*$/, '')
        .split('n')
        .map(str => str.replace(/s*$/, ''));

    main();
});

function readLine() {
    return inputString[currentLine++];
}

function Node() {
    this.index = [];
    this.indexH = [];
    this.children = {};
}

function Trie() {
    var root = new Node();
    function add(word, node, index, health) {
        var char, previousHealth = 0, len;
        if (word === '') {
            len = node.index.length;
            if (len) {
                previousHealth = node.indexH[len-1];
            }
            node.index.push(index);
            node.indexH.push(health + previousHealth);
            return;
        }
        char = word[0];
        if (!node.children[char]) {
            node.children[char] = new Node();
        }
        add(word.substr(1), node.children[char], index, health);
    }
    return {
        add: function(word, index, health) {
            add(word, root, index, health);
        },
        getRoot: function() {
            return root;
        }
    }
}

function findIndex(arr, start, end, val) {
    var index = Math.floor((end - start) / 2) + start;
    if (arr[index] === val) return index;
    if (arr[start] === val) return start;
    if (arr[end] === val) return end;
    if (arr[index] > val) {
        end = index;
    } else {
        start = index;
    }
    if (end - start <= 1) {
        if (arr[end] < val) {
            return end;
        }
        return start;
    }
    return findIndex(arr, start, end, val);
}

function main() {
    const n = parseInt(readLine(), 10);

    const genes = readLine().split(' ');

    const health = readLine().split(' ').map(healthTemp => parseInt(healthTemp, 10));
    const s = parseInt(readLine(), 10);
    var trie = new Trie();
    var min = null;
    var max = null;

    genes.forEach((gene, index) => {
        trie.add(gene, index, health[index]);
    });
    for (let sItr = 0; sItr < s; sItr++) {
        const firstLastd = readLine().split(' ');

        const first = parseInt(firstLastd[0], 10);

        const last = parseInt(firstLastd[1], 10);

        const d = firstLastd[2];
        var len = d.length;
        var dnaHealth = 0;

        var getSum = function(cn) {
            var cnIndexLen = cn.index.length;
            var startIndex, endIndex;
            if (cnIndexLen === 0) return;
            startIndex = findIndex(cn.index, 0, cnIndexLen - 1, first - 1);
            endIndex = findIndex(cn.index, 0, cnIndexLen - 1, last);
            if (cn.index[endIndex] <= last) {
                dnaHealth += cn.indexH[endIndex];
            }
            if (cn.index[startIndex] < first) {
                dnaHealth -= cn.indexH[startIndex];
            }
        };

        for (let i = 0; i < len; i++) {
            var iter = i;
            var node = trie.getRoot();
            do {
                node = node.children[d[iter++]];
                if (!node) {
                    break;
                }
                getSum(node);
            } while(iter < len);
        }

        min = min === null ? dnaHealth : Math.min(min, dnaHealth);
        max = max === null ? dnaHealth : Math.max(max, dnaHealth);
    }
    console.log(`${min} ${max}`)
}