Hackerrank Determining DNA Health problem solution

In this Hackerrank Determining DNA Health problem we have given an array of numbers with a given DNA standard and we need to find and print the respective strands of DNA as two space-separated values on a single line.

Problem solution in Python programming.

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)

Problem solution in Java Programming.

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}`)
}