Javascript Program to Find Maximum number of 0s placed consecutively at the start and end in any rotation of a Binary String
Given a binary string S of size N, the task is to maximize the sum of the count of consecutive 0s present at the start and end of any of the rotations of the given string S.
Examples:
Input: S = β1001β
Output: 2
Explanation:
All possible rotations of the string are:
β1001β: Count of 0s at the start = 0; at the end = 0. Sum= 0 + 0 = 0.
β0011β: Count of 0s at the start = 2; at the end = 0. Sum = 2 + 0=2
β0110β: Count of 0s at the start = 1; at the end = 1. Sum= 1 + 1 = 2.
β1100β: Count of 0s at the start = 0; at the end = 2. Sum = 0 + 2 = 2
Therefore, the maximum sum possible is 2.Input: S = β01010β
Output: 2
Explanation:
All possible rotations of the string are:
β01010β: Count of 0s at the start = 1; at the end = 1. Sum= 1+1=1
β10100β: Count of 0s at the start = 0; at the end = 2. Sum= 0+2=2
β01001β: Count of 0s at the start = 1; at the end = 0. Sum= 1+0=1
β10010β: Count of 0s at the start = 0; at the end = 1. Sum= 0+1=1
β00101β: Count of 0s at the start = 2; at the end = 0. Sum= 2+0=2
Therefore, the maximum sum possible is 2.
Naive Approach: The simplest idea is to generate all rotations of the given string and for each rotation, count the number of 0s present at the beginning and end of the string and calculate their sum. Finally, print the maximum sum obtained.
Below is the implementation of the above approach:
Javascript
<script> // Javascript program for the above approach // Function to find the maximum sum of // consecutive 0s present at the start // and end of a string present in any // of the rotations of the given string function findMaximumZeros(str, n) { // Check if all the characters // in the string are 0 var c0 = 0; var i; // Iterate over characters // of the string for (i = 0; i < n; ++i) { if (str[i] == '0' ) c0++; } // If the frequency of '1' is 0 if (c0 == n) { // Print n as the result document.write(n); return ; } // Concatenate the string // with itself var s = str + str; // Stores the required result var mx = 0; var j; // Generate all rotations of the string for (i = 0; i < n; ++i) { // Store the number of consecutive 0s // at the start and end of the string var cs = 0; var ce = 0; // Count 0s present at the start for (j = i; j < i + n; ++j) { if (s[j] == '0' ) cs++; else break ; } // Count 0s present at the end for (j = i + n - 1; j >= i; --j) { if (s[j] == '0' ) ce++; else break ; } // Calculate the sum var val = cs + ce; // Update the overall // maximum sum mx = Math.max(val, mx); } // Print the result document.write(mx); } // Driver Code // Given string var s = "1001" ; // Store the size of the string var n = s.length; findMaximumZeros(s, n); </script> |
2
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: The idea is to find the maximum number of consecutive 0s in the given string. Also, find the sum of consecutive 0s at the start and the end of the string, and then print the maximum out of them.
Follow the steps below to solve the problem:
- Check if the frequency of β1β in the string, S is equal to 0 or not. If found to be true, print the value of N as the result.
- Otherwise, perform the following steps:
- Store the maximum number of consecutive 0s in the given string in a variable, say X.
- Initialize two variables, start as 0 and end as N-1.
- Increment the value of cnt and start by 1 while S[start] is not equal to β1β.
- Increment the value of cnt and decrement end by 1 while S[end] is not equal to β1β.
- Print the maximum of X and cnt as a result.
Below is the implementation of the above approach:
Javascript
<script> //Javascript program for //the above approach // Function to find the maximum sum of // consecutive 0s present at the start // and end of any rotation of the string str function findMaximumZeros(str, n) { // Stores the count of 0s var c0 = 0; for ( var i = 0; i < n; ++i) { if (str[i] == '0' ) c0++; } // If the frequency of '1' is 0 if (c0 == n) { // Print n as the result document.write( n); return ; } // Stores the required sum var mx = 0; // Find the maximum consecutive // length of 0s present in the string var cnt = 0; for ( var i = 0; i < n; i++) { if (str[i] == '0' ) cnt++; else { mx = Math.max(mx, cnt); cnt = 0; } } // Update the overall maximum sum mx = Math.max(mx, cnt); // Find the number of 0s present at // the start and end of the string var start = 0, end = n - 1; cnt = 0; // Update the count of 0s at the start while (str[start] != '1' && start < n) { cnt++; start++; } // Update the count of 0s at the end while (str[end] != '1' && end >= 0) { cnt++; end--; } // Update the maximum sum mx = Math.max(mx, cnt); // Print the result document.write( mx); } var s = "1001" ; // Store the size of the string var n = s.length; findMaximumZeros(s, n); // This code is contributed by SoumikMondal </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Please refer complete article on Maximum number of 0s placed consecutively at the start and end in any rotation of a Binary String for more details!