Description

Given a binary string str of length N. The task is to split the input
string into substring of length L, find the substring that has the maximum
occurrence of 1s, count the total number of 1s in that substring and give
this number as the output.

For Example - 
str="0001110101"
L=3
The binary string has three substring of length 3: "000","111" and "010"
and a substring "1". The second substring has the maximum number of 1s equal
to 3, so the output is 3.

Note: If N is not a multiple of L, then the last substring of length less than
L should also be taken into the consideration.

For complete code follow below program.

C/C++

/* C Program to find maximum number of 1s in a substring of a String */
//Save it as CountOneInBinaryString.c


#include<stdio.h>
#include<string.h>
#include<limits.h>
int main(){

    char myStr[100];
    int i, j, l, len;

    printf("Enter a binary String : ");
    gets(myStr);

    len = strlen(myStr);

    printf("Enter the value of L : ");
    scanf("%d",&l);

    //Declaring the maximum value fo finding maximum count of 1
    //if predefine function is not working declare the max=0
    int max = INT_MIN;

    //it for finding next value of i from which the loop start in next turn
    int val = 0;


    //Loop through complete string
    for(i=0;i<len;i++) {
        //Count is for counting 1 in substring
        int count = 0;

        //This is for loop should not exceed the length of string
        int maxLength;
        if((i+l)> len) {
            maxLength = len;
        }else {
            maxLength = (i+l);
        }


        //Checking number of 1's in given substring
        for(j=i;j<maxLength;j++) {
            if(myStr[j] == '1') {
                count++;
            }
        }
        if(count > max) {
            max = count;
        }

        val++;

        //finding i for next turn(subtracting 1 because i will increase 1 because of for loop)
        i = (val * l)-1;
    }
    printf("max : %d",max);

    return 0;
}

Input:
Enter a binary String : 1000011
Enter the value of L : 5

Output:
max : 2

Java

/* Java Program to find maximum number of 1s in a substring of a String */
//Save it as CountOneInBinaryString.java


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

public class CountOneInBinaryString {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        
        System.out.println("Enter a binary String : ");
        String str = scanner.nextLine();
        
        System.out.println("Enter the value of L : ");
        int l = scanner.nextInt();
        
                //Converting string to character array
        char myStr[] = str.toCharArray();
        
                //Declaring the maximum value fo finding maximum count of 1
                //if predefine function is not working declare the max=0
        int max = Integer.MIN_VALUE;
        
                //it for finding next value of i from which the loop start in next turn
        int val = 0;
        
        
                //Loop through complete string
        for(int i=0;i<myStr.length;i++) {
                        //Count is for counting 1 in substring
            int count = 0;
            
                        //This is for loop should not exceed the length of string
            int maxLength;
            if((i+l)> myStr.length) {
                maxLength = myStr.length;
            }else {
                maxLength = (i+l);
            }
            
            
                        //Checking number of 1's in given substring
            for(int j=i;j<maxLength;j++) {
                if(myStr[j] == '1') {
                    count++;
                }
            }
            if(count > max) {
                max = count;
            }
            
            val++;
            
                        //finding i for next turn(subtracting 1 because i will increase 1 because of for loop)
            i = (val * l)-1;
        }
        System.out.println("max : "+max);		
    }
}

Input:
Enter a binary String : 
0001110101
Enter the value of L : 
3

Output:
max : 3

Related Programs