HackerRank Determining DNA Health Solution

Hello Programmers, In this post, you will learn how to solve HackerRank Determining DNA Health Solution. This problem is a part of the HackerRank Algorithms Series.

Ezoicreport this adHackerRank Determining DNA Health Solution
HackerRank Determining DNA Health Solution

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Hackerrank by yourself. If you find any difficulty after trying several times, then you can look for solutions.

HackerRank Determining DNA Health Solution

Task

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 DNAtotal 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 = [g0g1, . . . , gn-1]. Note that these gene sequences are not guaranteed to be distinct.
  • An array of gene health values, health = [h0h1, . . . , hn-1], where each hi is the health value for gene gi.
  • A set of s DNA strands where the definition of each strand has three components, startend, and d, where string d 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.

Input Format

The first line contains an integer, n, denoting the total number of genes.
The second line contains n spaceseparated strings describing the respective values of g0g1, . . . , gn-1 (i.e., the elements of genes).
The third line contains n space-separated integers describing the respective values of h0h1, . . . , hn-1 (i.e., the elements of health).
The fourth line contains an integer, s, denoting the number of strands of DNA to process.
Each of the s subsequent lines describes a DNA strand in the form start end d, denoting that the healthy genes for DNA strand d are gstart, . . . , gend and their respective correlated health values are hstart, . . . , hend.

Constraints

  • 1 <= ns <= 105
  • 0 <= hi <= 107
  • 0 <= first <= last < n
  • 1 <= the sum of the lengths of all genes and DNA strands <= 2 x 106
  • It is guaranteed that each gi consists of lowercase English alphabetic letters only (i.e., a to z).

Output Format

Print two spaceseparated 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

Explanation 0

In the diagrams below, the ranges of beneficial genes for a specific DNA on the left are highlighed in green and individual instances of beneficial genes on the right are bolded. The total healths of the s = 3 strands are:

  1. image
    The total health of caaab is 3 + 4 + 4 + 2 + 6 = 19.
  2. image
    The total health of xyz is 0, because it contains no beneficial genes.
  3. image
    The total health of bcdybc is 3 + 5 + 3 = 11.

The unhealthiest DNA strand is xyz with a total health of 0, and the healthiest DNA strand is caaab with a total health of 19. Thus, we print 0 19 as our answer.

HackerRank Determining DNA Health Solution

HackerRank Determining DNA Health Solution in C

#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 != '\0') { 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 != '\0') { 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 != '\0') { 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 != '\0') { 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 != '\0') { 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] = '\0';
    }
    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;
}

HackerRank Determining DNA Health Solution in Cpp

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;
typedef long long LL;
typedef vector<int> VI;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}
struct PMA {
    struct Node {
	Node *ch, *sib, *fail;
	char c;
	LL cnt;
        Node() : ch(0), sib(0), fail(0), c(0), cnt(0) { }
	struct Iter {
	    Node *x;
	    Iter(Node *x_) : x(x_) {}
	    operator Node*() { return x; }
	    Node *operator->() { return x; }
	    void operator++() { x = x->sib; }
	    bool operator!=(const Iter & y) const { return x != y.x; }
	    bool operator==(const Iter & y) const { return x == y.x; }
	};
	Iter begin() { return ch; }
	Iter end() { return NULL; }
    };
    Node *root, *nodes;
    int nodes_i;
    PMA() { }
    PMA(const vector<string> &d, const vector<int> &g) {
	int len = 0;
	REP (i, d.size()) len += d[i].size();
	len++;
	nodes_i = 0;
	nodes = new Node[len];
	root = new_node();
	// Trie
	REP (i, d.size()) {
	    Node *x = root;
	    const string &s = d[i];
	    REP (j, s.size()) x = get_child(x, s[j], true);
	    x->cnt += g[i];
	}
	// failure link, bfs
	vector<Node*> ord; ord.reserve(nodes_i);
	ord.push_back(root);
	for (int i=0; i<nodes_i; i++) {
	    Node *x = ord[i];
	    EACH (ch, *x) ord.push_back(ch);
	}
	root->fail = root; // ord[0]
	EACH (x, *root) x->fail = root;
	for (int i=1; i<nodes_i; i++) {
	    Node *x = ord[i];
	    EACH (ch, *x) {
		Node *f = x->fail, *y;
		while (!(y=get_child(f, ch->c)) && f != root) f = f->fail;
		ch->fail = y ?: root;
	    }
	}
	// accumulate
	REP (i, nodes_i) ord[i]->cnt += ord[i]->fail->cnt;
    }
    Node *new_node() {
	return &nodes[nodes_i++];
    }
    Node *get_child(Node *x, char c, bool create=false) { // assert(x != NULL);
	if (!x->ch) {
	    if (create) {
		x->ch = new_node();
		x->ch->c = c;
	    }
	    return x->ch;
	} else {
	    EACH (ch, *x) {
		if (ch->c == c) return ch;
		if (create && !ch->sib) {
		    ch->sib = new_node();
		    ch->sib->c = c;
		    return ch->sib;
		}
	    }
	    return NULL;
	}
    }
    // Aho Corasick
    LL match(const string &s) {
	Node *x = root;
	LL ret = 0;
	REP (i, s.size()) {
	    Node *y = NULL;
	    while (!(y=get_child(x, s[i])) && x != root) x = x->fail;
	    x = y ?: root;
	    ret += x->cnt;
	}
	return ret;
    }
    void clear() {
	delete[] nodes;
	root = nodes = NULL;
	nodes_i = 0;
    }
};
int N;
char buf[2000111];
string S[100111];
int H[100111];
int Q;
string W[100111];
LL ans[100111];
const int MAXN = 1<<17;
VI ids[1<<18];
int L, R, id;
void add(int l, int r, int k) {
    if (L <= l && r <= R) {
	ids[k].push_back(id);
    } else if (R <= l || r <= L) {
    } else {
	add(l, (l+r)/2, k+k);
	add((l+r)/2, r, k+k+1);
    }
}
void calc(int l, int r, int k) {
    if (k < 2 * MAXN) {
	if (ids[k].size()) {
	    PMA pma(vector<string>(S+l, S+r), VI(H+l, H+r));
	    EACH (e, ids[k]) {
//		eprintf("%d %d : %s %lld\n", l, r, W[*e].c_str(), pma.match(W[*e]));
		ans[*e] += pma.match(W[*e]);
	    }
	    pma.clear();
	}
	calc(l, (l+r)/2, k+k);
	calc((l+r)/2, r, k+k+1);
    }
}
int main() {
    scanf("%d", &N);
    REP (i, N) {
	scanf("%s", buf);
	S[i] = buf;
    }
    REP (i, N) scanf("%d", H+i);
    scanf("%d", &Q);
    REP (i, Q) {
	scanf("%d%d%s", &L, &R, buf);
	R++;
	id = i;
	W[i] = buf;
	add(0, MAXN, 1);
    }
    calc(0, MAXN, 1);
    auto p = minmax_element(ans, ans + Q);
    printf("%lld %lld\n", *p.first, *p.second);
    return 0;
}

HackerRank Determining DNA Health Solution in Java

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.Queue;
public class C3 {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		int n = ni();
		char[][] ss = new char[n][];
		for(int i = 0;i < n;i++){
			ss[i] = ns().toCharArray();
		}
		int[] h = na(n);
		
		int Q = ni();
		char[][] qs = new char[Q][];
		long[] es = new long[2*Q];
		for(int i = 0;i < Q;i++){
			int s = ni(), t = ni();
			qs[i] = ns().toCharArray();
			es[i] = (long)s<<32|(long)i<<1|0;
			es[i+Q] = (long)t+1<<32|(long)i<<1|1;
		}
		Arrays.sort(es);
		long[] rets = new long[Q];
		TrieByLink[] tries = new TrieByLink[18];
		int p = 0;
		for(long e : es){
			long x = e>>>32;
			int ind = ((int)e)>>>1;
			int pm = (e&1) == 0 ? -1 : 1;
			while(p < n && p <= x-1){
				int d = Integer.numberOfTrailingZeros(p+1);
				tries[d] = new TrieByLink();
				for(int k = p-(1<<d)+1;k <= p;k++){
					tries[d].add(ss[k], h[k]);
				}
				tries[d].buildFailure();
				p++;
			}
			long lhit = 0;
			for(int d = 0;d < 18;d++){
				if(p<<~d<0){
					lhit += tries[d].countHit(qs[ind]);
				}
			}
			rets[ind] += lhit*pm;
		}
		long min = Long.MAX_VALUE;
		long max = Long.MIN_VALUE;
		for(long r : rets)min = Math.min(min, r);
		for(long r : rets)max = Math.max(max, r);
		
		out.println(min + " " + max);
	}
	
	public static class TrieByLink {
		public Node root = new Node((char)0, 0);
		public int gen = 1;
		public static final char[] atoz = "abcdefghijklmnopqrstuvwxyz".toCharArray();
		
		public static class Node
		{
			public int id;
			public char c;
			public Node next, firstChild;
			public long hit = 0;
			
			public Node fail;
			
			public Node(char c, int id)
			{
				this.id = id;
				this.c = c;
			}
			
			public String toString(String indent)
			{
				StringBuilder sb = new StringBuilder();
				sb.append(indent + id + ":" + c);
				if(hit != 0)sb.append(" H:" + hit);
				if(fail != null)sb.append(" F:" + fail.id);
				sb.append("\n");
				for(Node c = firstChild;c != null; c = c.next){
					sb.append(c.toString(indent + "  "));
				}
				return sb.toString();
			}
		}
		
		public void add(char[] s, long hit)
		{
			Node cur = root;
			Node pre = null;
			for(char c : s){
				pre = cur; cur = cur.firstChild;
				if(cur == null){
					cur = pre.firstChild = new Node(c, gen++);
				}else{
					for(;cur != null && cur.c != c;pre = cur, cur = cur.next);
					if(cur == null)cur = pre.next = new Node(c, gen++);
				}
			}
			cur.hit += hit;
		}
		
		public void buildFailure()
		{
			root.fail = null;
			Queue<Node> q = new ArrayDeque<Node>();
			q.add(root);
			while(!q.isEmpty()){
				Node cur = q.poll();
				inner:
				for(Node ch = cur.firstChild;ch != null; ch = ch.next){
					q.add(ch);
					for(Node to = cur.fail; to != null; to = to.fail){
						for(Node lch = to.firstChild;lch != null; lch = lch.next){
							if(lch.c == ch.c){
								ch.fail = lch;
								ch.hit += lch.hit; // propagation of hit
								continue inner;
							}
						}
					}
					ch.fail = root;
				}
			}
		}
		
		public Node next(Node cur, char c)
		{
			for(;cur != null;cur = cur.fail){
				for(Node ch = cur.firstChild;ch != null; ch = ch.next){
					if(ch.c == c)return ch;
				}
			}
			return root;
		}
		
		public int[][] ngMatrix(char[] cs)
		{
			int[] map = new int[128];
			Arrays.fill(map, -1);
			for(int i = 0;i < cs.length;i++)map[cs[i]] = i;
			
			int[][] a = new int[gen+1][gen+1];
			Node[] nodes = toArray();
			for(int i = 0;i < gen;i++){
				if(nodes[i].hit > 0)continue;
				int nohit = cs.length;
				boolean[] ved = new boolean[cs.length];
				for(Node cur = nodes[i];cur != null;cur = cur.fail){
					for(Node ch = cur.firstChild;ch != null; ch = ch.next){
						if(map[ch.c] >= 0 && !ved[map[ch.c]]){
							ved[map[ch.c]] = true;
							if(ch.hit == 0)a[ch.id][i]++;
							nohit--;
						}
					}
				}
				a[0][i] += nohit;
			}
			Arrays.fill(a[gen], 1);
			return a;
		}
		
		public int[][] okMatrix(char[] cs)
		{
			int[] map = new int[128];
			Arrays.fill(map, -1);
			for(int i = 0;i < cs.length;i++)map[cs[i]] = i;
			
			int[][] a = new int[gen+1][gen+1];
			Node[] nodes = toArray();
			for(int i = 0;i < gen;i++){
				if(nodes[i].hit > 0)continue;
				int nohit = cs.length;
				boolean[] ved = new boolean[cs.length];
				for(Node cur = nodes[i];cur != null;cur = cur.fail){
					for(Node ch = cur.firstChild;ch != null; ch = ch.next){
						if(map[ch.c] >= 0 && !ved[map[ch.c]]){
							ved[map[ch.c]] = true;
							if(ch.hit > 0){
								a[gen][i]++;
							}else{
								a[ch.id][i]++;
							}
							nohit--;
						}
					}
				}
				a[0][i] += nohit;
			}
			a[gen][gen]++;
			return a;
		}
		
		public void search(char[] q)
		{
			Node cur = root;
			outer:
			for(char c : q){
				for(;cur != null;cur = cur.fail){
					for(Node ch = cur.firstChild;ch != null; ch = ch.next){
						if(ch.c == c){
							// ch.hit
							cur = ch;
							continue outer;
						}
					}
				}
				cur = root;
			}
		}
		
		public long countHit(char[] q)
		{
			Node cur = root;
			long hit = 0;
			outer:
			for(char c : q){
				for(;cur != null;cur = cur.fail){
					for(Node ch = cur.firstChild;ch != null; ch = ch.next){
						if(ch.c == c){
							hit += ch.hit; // add hit
							cur = ch;
							continue outer;
						}
					}
				}
				cur = root;
			}
			return hit;
		}
		
		public Node[] toArray()
		{
			Node[] ret = new Node[gen];
			ret[0] = root;
			for(int i = 0;i < gen;i++){
				Node cur = ret[i];
				if(cur.next != null)ret[cur.next.id] = cur.next;
				if(cur.firstChild != null)ret[cur.firstChild.id] = cur.firstChild;
			}
			return ret;
		}
		
		public String toString()
		{
			return root.toString("");
		}
	}
	
	void run() throws Exception
	{
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
	}
	
	public static void main(String[] args) throws Exception { new C3().run(); }
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
	
	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
Ezoicreport this ad

HackerRank Determining DNA Health Solutions 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 Solutions using JavaScript

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

HackerRank Determining DNA Health Solutions in Scala

Ezoicreport this adHackerRank Determining DNA Health Solutions in Pascal

Disclaimer: This problem (Determining DNA Health) is generated by HackerRank but the Solution is Provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.

Next: HackerRank Palindrome Index Solution

Sharing Is Caring

Leave a Comment

Ezoicreport this ad