HackerRank Bear and Steady Gene problem solution

In this HackerRank Bear and Steady Gene problem solution, we have given a string that represents the DNA of the bear. and we need to find the length of the smallest substring to replace in the string to make changes in the DNA.

Problem solution in Python.

from collections import Counter
import sys
import math

n = int(input())
s1 = input()
s = Counter(s1)

if all(e <= n/4 for e in s.values()):
    print(0)
    sys.exit(0)

result = float("inf")
out = 0
for mnum in range(n):
    s[s1[mnum]] -= 1
    while all(e <= n/4 for e in s.values()) and out <= mnum:
        result = min(result, mnum - out + 1)
        s[s1[out]] += 1
        out += 1

print(result)

{"mode":"full","isActive":false}

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        String s = in.next();
        String genes = "ATGC";
        int [] cnt = new int[4];
        int left = 0;
        for(int i=0;i<n;i++){
            int cur = genes.indexOf(s.charAt(i));
            if(cnt[cur] + 1 > n / 4) {left = i-1; break;}
            cnt[cur] ++ ;
        }
        if(left == 0){
            System.out.println(0);
            return;
        }
        int res = n;
        int right = n-1;
        for(int i = left; i >= 0; i--){
            int cur;
            while(right>0){
                cur = genes.indexOf(s.charAt(right));
                if(cnt[cur] + 1 > n/4) break;
                cnt[cur]++;
                right -- ;
            }
            cur = genes.indexOf(s.charAt(i));
            cnt[cur] -- ;
            res = Math.min(res, right-i);
        }
        System.out.println(res);
    }
}

{"mode":"full","isActive":false}

Problem solution in C++.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    int n;
    cin >> n;
    string s;
    cin >> s;
    unordered_map<char, int> map, check_map;
    vector<int> vec;

    //histogram
    for(char c: s){
        if(map.count(c)){
            map.find(c)->second++;
        }else{
            map.insert({c,1});
        }
    }
    int minimum = 0;
    for(auto& c: map){
        if(c.second > n/4){
            minimum += c.second - n/4;
            check_map.insert({c.first, c.second - n/4});            
        }     
    }

    if(check_map.empty()) {
        cout << 0 << endl;
        return 0;
    }

    for(int i = 0; i < n; i++){
        if(check_map.count(s[i])){
            vec.push_back(i);
        }
    }
    
    int min = n;
    bool flag;

    for(int k = 0; k < minimum; k++)
        check_map.find(s[vec[k]])->second--;
    int j = minimum - 1;
    for(int i = 0; i < vec.size() - minimum; i++){
        int left = vec[i];
        while(1){
            flag = true;
            for(auto& c: check_map){ // check if all redundent is zero
                if(c.second > 0)
                    flag = false;
            }
            if(flag || (j + 1) == vec.size())
                break;
            j++;
            check_map.find(s[vec[j]])->second--;
        }
        int right = vec[j];
        if(min > right - left + 1 && flag)
             min = right - left + 1;
        if(min == minimum){
            cout << minimum << endl;
            return 0;
        }
        check_map.find(s[vec[i]])->second++;
    }
    cout << min << endl;
    return 0;
}

{"mode":"full","isActive":false}

Problem solution in C.

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

#define LETTER_TO_INDEX(a)  (((a) >> 1) & 0x3)
char lets[] = {
    'A',
    'C',
    'T', 
    'G'
};

int forward[4][500001];
int backward[4][500001];
int lookup[4][500002];

int main() {
    int i, j, n, count;
    char input[500000];
    
    scanf("%d", &n);
    scanf("%s", input);
    for (j = 0; j < 4; j++) {
        for (i = 0; i < n; i++) {
            forward[j][i + 1] = forward[j][i] + (LETTER_TO_INDEX(input[i]) == j);
            backward[j][i + 1] = backward[j][i] + (LETTER_TO_INDEX(input[n - i - 1]) == j);
        }
    }
    
    memset(lookup, -1, sizeof(int) * 4 * 500002);
    for (j = 0; j < 4; j++) {
        lookup[j][0] = n;
        for (i = 1; i <= n; i++) {
            if (backward[j][i] != backward[j][i - 1] || i == n) {
                lookup[j][backward[j][i - 1]] = n - i + 1;
            }
        }
    }
        
    int needed = n / 4;
    int min_len = n;
    int l_max;
    int l_len;
    int pos;
    for (i = 0; i < n; i++) {
        l_max = 0;
        for (j = 0; j < 4; j++) {
            if (forward[j][i] > needed) {
                l_max = -1;
                break;
            } 
            pos = lookup[j][needed - forward[j][i]];
            if (pos > l_max)
                l_max = pos;
        }
        if (l_max != -1 && l_max - i < min_len) {
            min_len = l_max - i;
        }
    }
    printf("%d\n", min_len);
    
    return 0;
}

{"mode":"full","isActive":false}