HackerRank Bear and Steady Gene problem solution

HackerRank Bear and Steady Gene problem solution – In this HackerRank Bear and Steady Gene problem Bear Limak is a famous biotechnology scientist who specializes in modifying bear DNA to make it steady. Right now, he is examining a gene represented as a string gene. It is not necessarily steady. Fortunately, Limak can choose one (maybe empty) substring of gene and replace it with any string of the same length.

Modifying a large substring of bear genes can be dangerous. Given a string gene, can you help Limak find the length of the smallest possible substring that he can replace to make gene a steady gene?

HackerRank Bear and Steady Gene 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)

Bear and Steady Gene 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);
    }
}

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

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("%dn", min_len);
    
    return 0;
}