Balance String

You are a high school teacher and on the occasion of Children's day, you have decided to give away a bunch of chocolates to your class!
Unfortunately, you notice that only 4 students have come to class that day and so you end up having to give each of them multiple chocolates.
(Each of the four students present is identified by their roll numbers which can range from 1 to 4 ) 

After distributing the chocolates, you notice that some kids have received more chocolates than others and this has made some of the kids very upset.

It is your job now to remedy this situation.
You have before you a long string equal in length to the number of chocolates, denoting which chocolate was given to which student. If the ith chocolate was given to the kid with roll no, 2, then the ith character of this string will be 2.
Since the operation of redistribution is somewhat tedious, you want to find the smallest possible substring and replace it with any substring of your choice, such that each student will now have the same number of Chocolates.

Example:

Input:  n=8, str = "31114111"
Output: 5

Approach

Java

import java.util.HashMap;
import java.util.Map;

public class BalanceString {
    public static void main(String[] args) {
        int n = 8;
        String str = "31114111";
        int N = n / 4;
        System.out.println(min_result(N, str));
    }

    public static int min_result(int NString str) {
        Map<CharacterIntegerm1 = new HashMap<CharacterInteger>();
        m1.put('1'0);
        m1.put('2'0);
        m1.put('3'0);
        m1.put('4'0);
        for (int i = 0; i < str.length(); ++i) {
            m1.put(str.charAt(i), m1.get(str.charAt(i)) + 1);
        }
        int min = Integer.MAX_VALUE;
        int x = 0;
        int y = 0;
        while (x < str.length() && y < str.length()) {
            if (!check_equal(N, m1)) {
                m1.put(str.charAt(y), m1.get(str.charAt(y)) - 1);
                y++;
            } else {
                min = Math.min(min, y - x);
                m1.put(str.charAt(x), m1.get(str.charAt(x)) + 1);
                x++;
            }
        }
        return min;
    }

    public static boolean check_equal(int NMap<CharacterIntegerm2) {
        if (m2.get('1') <= N && m2.get('2') <= N && m2.get('3') <= N && m2.get('4') <= N)
            return true;
        return false;
    }
}


No comments:

Post a Comment