Skip to content
Programmingoneonone
Programmingoneonone

LEARN EVERYTHING ABOUT PROGRAMMING

  • Home
  • CS Subjects
    • IoT ? Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

LEARN EVERYTHING ABOUT PROGRAMMING

HackerRank Save Humanity problem solution

YASH PAL, 31 July 2024

In this HackerRank Save Humanity problem solution, we have given the DNA of the patient as well as of the virus consists of lowercase letters. Since the collected data is raw, there may be some errors. You will need to find all substrings in the patient DNA that either exactly match the virus DNA or have at most one mismatch, i.e., a difference in at most one location.

HackerRank Save Humanity problem solution

Topics we are covering

Toggle
  • Problem solution in Python.
  • Problem solution in Java.
  • Problem solution in C++.
  • Problem solution in C.

Problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'virusIndices' function below.
#
# The function accepts following parameters:
#  1. STRING p
#  2. STRING v
#
def small_match(w1, w2):
    counter = 0
    for i in range(len(w1)):
        if w1[i] != w2[i]:
            counter += 1
            if counter > 1:
                return 0
    return 1


def match(w1, w2):
    length = len(w1)
    if length < 10:
        return small_match(w1, w2)
    w11 = w1[:length // 2]
    w12 = w1[length // 2:]
    w21 = w2[:length // 2]
    w22 = w2[length // 2:]

    s1 = (w11 == w21)
    s2 = (w12 == w22)

    if s1 and s2:
        return True
    elif s1 and not s2:
        return match(w12, w22)
    elif not s1 and s2:
        return match(w11, w21)
    else:
        return False


def virusIndices(p, v):

    res = ''
    if len(v) > len(p):
        return "No Match!"
    else:
        for i in range(len(p) - len(v) + 1):
            temp = p[i:i + len(v)]

            flag = match(temp, v)
            if flag:
                res += str(i) + ' '
        if len(res) == 0:
            return "No Match!"
        else:
            return res.strip()

if __name__ == '__main__':
    t = int(input().strip())

    for t_itr in range(t):
        first_multiple_input = input().rstrip().split()

        p = first_multiple_input[0]

        v = first_multiple_input[1]

        print(virusIndices(p, v))

{“mode”:”full”,”isActive”:false}

Problem solution in Java.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

import java.util.stream.Collectors;

public class Solution {

    /*
     * Complete the virusIndices function below.
     */
    static List<Integer> virusIndices(String p, String v) {
        List<Integer> z = z_function(v + "#" + p);
        List<Integer> z_reversed = z_function(new StringBuilder(v).reverse().toString() + "#" + new StringBuilder(p).reverse().toString());
        List<Integer> answer = new ArrayList<>();
        for (int i = 0; i <= p.length() - v.length(); ++i) {
            if (z.get(i + v.length() + 1) + z_reversed.get(p.length() - i + 1) >= v.length() - 1) {
                answer.add(i);
            }
        }
        return answer;
    }

    private static List<Integer> z_function(String s) {
        List<Integer> z = new ArrayList(s.length());
        z.add(0);
        int l = 0;
        int r = 0;
        for (int i = 1; i < s.length(); ++i) {
            int z_i = 0;
            if (i <= r)
                z_i = r - i + 1 < z.get(i - l) ? r - i + 1 : z.get(i - l);
            while (i + z_i < s.length() && s.charAt(z_i) == s.charAt(i + z_i)) 
                ++z_i;
            if (i + z_i - 1 > r) {
                l = i;
                r = i + z_i - 1;
            }
            z.add(z_i);
        }
        return z;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        int t = Integer.parseInt(scanner.nextLine().trim());

        for (int tItr = 0; tItr < t; tItr++) {
            String[] pv = scanner.nextLine().split(" ");

            String p = pv[0];

            String v = pv[1];

            List<Integer> answer = virusIndices(p, v);
            if (answer.size() == 0) {
                System.out.println("No Match!");
            } else {
                System.out.println(answer.stream().map(String::valueOf).collect(Collectors.joining(" ")));
            }
        }
    }
}

{“mode”:”full”,”isActive”:false}

Problem solution in C++.

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MaxN = 200005;

void e_kmp(char *s, char *t, int *has, int *e_has)
{
	int sp, p, mx, tn;
	for (sp = p = mx = 0; s[p] > 0; p++)
	{
		if (mx == p || p + e_has[p - sp] >= mx)
		{
			for (tn = mx - p; s[mx] == t[tn]; tn++)
				mx++;
			has[sp = p] = mx - p;
			if (mx == p)
				sp = mx = p + 1;
		}
		else
			has[p] = e_has[p - sp];
	}
}
char s[MaxN],t[MaxN];
int A[MaxN],B[MaxN],A2[MaxN],B2[MaxN];
int ans[MaxN],n,m;

int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		scanf("%s%s",s,t);
		n = strlen(s), m = strlen(t);
		t[m] = -1;
		A[0] = m;
		e_kmp(t+1,t,A+1,A);
		e_kmp(s,t,B,A);
		reverse(s,s+n);
		reverse(t,t+m);
		A2[0] = m;
		e_kmp(t+1,t,A2+1,A2);
		e_kmp(s,t,B2,A2);

		int cnt = 0;
		for(int i = 0; i+m-1 < n; i++)
		{
			if(B[i]>=m || B2[n-(i+m)]+B[i]>=m-1)
				ans[cnt++] = i;
		}
		for(int i = 0; i < cnt; i++)
			printf("%d%c",ans[i],i==cnt-1?'n':' ');
		if(cnt==0)puts("");
	}

	return 0;
}

{“mode”:”full”,”isActive”:false}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#define kMaxSize 100001
#define kMaxMismatch 1

typedef long long int lli;

int findDna8b(char* p, char* v, int vc);

int main()
{
    // Allocate memory for strings.
    char* p = (char*)malloc(kMaxSize * sizeof(char));
    char* v = (char*)malloc(kMaxSize * sizeof(char));
    
    // Test cases.
    int tc;
    scanf("%d", &tc);
    while (0 < tc--)
    {
        // Load strings.
        scanf("%s %s", p, v);
        int pc = (int)strlen(p);
        int vc = (int)strlen(v);
        
        // Look for v in p. Print starting index of each match.
        int c = (pc-vc);
        int matched = 0;
        for (int i = 0; i <= c; i++){
            if (findDna8b(&p[i], v, vc) == 1){
                matched++;
                printf("%d ", i);
            }
        }
        
        // We have to indicate if no matches were found.
        if (matched <= 0)
            printf("No Match!n");
        else
            printf("n");
    }
    
    return 0;
}

int findDna8b(char* p, char* v, int vc)
{
    lli* p8 = (lli*)p;
    lli* v8 = (lli*)v;
    
    int c = vc/8;
    int mismatch = 0;
    int i;
    for (i = 0; i < c; i++){
        if (p8[i] != v8[i])
        {
            for (int j = i*8; j < (i*8)+8; j++){
                if (p[j] != v[j]){
                    mismatch++;
                    if (mismatch > kMaxMismatch) return -1;
                }
            }
        }
    }
    
    for (int j = i*8; j < vc; j++){
        if (p[j] != v[j]){
            mismatch++;
            if (mismatch > kMaxMismatch) return -1;
        }
    }
    
    return 1;
}

{“mode”:”full”,”isActive”:false}

Algorithms coding problems solutions

Post navigation

Previous post
Next post
  • Automating Image Format Conversion with Python: A Complete Guide
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes