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