Bear and Steady Gene – HackerRank Solution

In this post, we will solve Bear and Steady Gene HackerRank Solution. This problem (Bear and Steady Gene) is a part of HackerRank Problem Solving series.

Solution – Bear and Steady Gene – HackerRank Solution

C++

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <map>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    char str[500001];
    scanf("%d %s",&n,str);
    int i=0, j=n-1, minl=n;
    int cnt[128] = {0};
    while (1)
    {
        if (j<0 || cnt[str[j]]==n/4)
        {
            j++;
            break;
        }
        else
        {
            cnt[str[j]]++;
            j--;
        }
    }
    if (j < minl)
        minl = j;
    for (i=0; i<n; i++)
    {
        cnt[str[i]]++;
        while (j<n && cnt[str[i]] > n/4)
        {
            cnt[str[j]]--;
            j++;
        }
        if (j==n)
            break;
        if (j-i-1 < minl)
            minl = j-i-1;
    }
    printf("%d\n",minl);
}

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)

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

Note: This problem (Bear and Steady Gene) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.