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.
Algorithm:
- Initialize a counter variable c0 to 0 to count the frequency of 0s in the given string.
- Traverse the string and for each character, if it is 0, increment the value of c0 by 1.
- If the value of c0 is equal to the length of the string n, it means that all the characters in the string are 0, so the maximum sum of consecutive 0s present at the start and end of the string will be n. Print n and return.
- Concatenate the string with itself and store it in a new string s.
- Initialize a variable mx to 0 to store the maximum sum of consecutive 0s present at the start and end of a string in any rotation of the given string.
- Generate all rotations of the string s using a loop that iterates from 0 to n-1.
- For each rotation, initialize two variables cs and ce to 0 to store the number of consecutive 0s at the start and end of the string, respectively.
- Traverse the rotated string from the current index i to i+n-1, and for each character, if it is 0, increment the value of cs by 1, else break out of the loop.
- Traverse the rotated string from the current index i+n-1 to i, and for each character, if it is 0, increment the value of ce by 1, else break out of the loop.
- Calculate the sum of cs and ce and store it in a variable val.
- Update the value of mx to the maximum of its current value and val.
- After the loop ends, the value of mx will contain the maximum sum of consecutive 0s present at the start and end of a string in any rotation of the given string. Print mx.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// 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 stringvoid findMaximumZeros(string str, int n){ // Check if all the characters // in the string are 0 int c0 = 0; // Iterate over characters // of the string for (int 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 cout << n; return; } // Concatenate the string // with itself string s = str + str; // Stores the required result int mx = 0; // Generate all rotations of the string for (int i = 0; i < n; ++i) { // Store the number of consecutive 0s // at the start and end of the string int cs = 0; int ce = 0; // Count 0s present at the start for (int j = i; j < i + n; ++j) { if (s[j] == '0') cs++; else break; } // Count 0s present at the end for (int j = i + n - 1; j >= i; --j) { if (s[j] == '0') ce++; else break; } // Calculate the sum int val = cs + ce; // Update the overall // maximum sum mx = max(val, mx); } // Print the result cout << mx;}// Driver Codeint main(){ // Given string string s = "1001"; // Store the size of the string int n = s.size(); findMaximumZeros(s, n); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// 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 stringstatic void findMaximumZeros(String str, int n){ // Check if all the characters // in the string are 0 int c0 = 0; // Iterate over characters // of the string for(int i = 0; i < n; ++i) { if (str.charAt(i) == '0') c0++; } // If the frequency of '1' is 0 if (c0 == n) { // Print n as the result System.out.print(n); return; } // Concatenate the string // with itself String s = str + str; // Stores the required result int mx = 0; // Generate all rotations of the string for(int i = 0; i < n; ++i) { // Store the number of consecutive 0s // at the start and end of the string int cs = 0; int ce = 0; // Count 0s present at the start for(int j = i; j < i + n; ++j) { if (s.charAt(j) == '0') cs++; else break; } // Count 0s present at the end for(int j = i + n - 1; j >= i; --j) { if (s.charAt(j) == '0') ce++; else break; } // Calculate the sum int val = cs + ce; // Update the overall // maximum sum mx = Math.max(val, mx); } // Print the result System.out.print(mx);}// Driver Codepublic static void main(String[] args){ // Given string String s = "1001"; // Store the size of the string int n = s.length(); findMaximumZeros(s, n);}}// This code is contributed by susmitakundugoaldanga |
Python3
# Python3 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 stringdef findMaximumZeros(st, n): # Check if all the characters # in the string are 0 c0 = 0 # Iterate over characters # of the string for i in range(n): if (st[i] == '0'): c0 += 1 # If the frequency of '1' is 0 if (c0 == n): # Print n as the result print(n) return # Concatenate the string # with itself s = st + st # Stores the required result mx = 0 # Generate all rotations of the string for i in range(n): # Store the number of consecutive 0s # at the start and end of the string cs = 0 ce = 0 # Count 0s present at the start for j in range(i, i + n): if (s[j] == '0'): cs += 1 else: break # Count 0s present at the end for j in range(i + n - 1, i - 1, -1): if (s[j] == '0'): ce += 1 else: break # Calculate the sum val = cs + ce # Update the overall # maximum sum mx = max(val, mx) # Print the result print(mx)# Driver Codeif __name__ == "__main__": # Given string s = "1001" # Store the size of the string n = len(s) findMaximumZeros(s, n) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;class GFG{// 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 stringstatic void findMaximumZeros(string str, int n){ // Check if all the characters // in the string are 0 int c0 = 0; // Iterate over characters // of the string for(int 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 Console.Write(n); return; } // Concatenate the string // with itself string s = str + str; // Stores the required result int mx = 0; // Generate all rotations of the string for(int i = 0; i < n; ++i) { // Store the number of consecutive 0s // at the start and end of the string int cs = 0; int ce = 0; // Count 0s present at the start for(int j = i; j < i + n; ++j) { if (s[j] == '0') cs++; else break; } // Count 0s present at the end for(int j = i + n - 1; j >= i; --j) { if (s[j] == '0') ce++; else break; } // Calculate the sum int val = cs + ce; // Update the overall // maximum sum mx = Math.Max(val, mx); } // Print the result Console.Write(mx);}// Driver Codepublic static void Main(string[] args){ // Given string string s = "1001"; // Store the size of the string int n = s.Length; findMaximumZeros(s, n);}}// This code is contributed by AnkThon |
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 stringfunction 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> |
Output:
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:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum sum of// consecutive 0s present at the start// and end of any rotation of the string strvoid findMaximumZeros(string str, int n){ // Stores the count of 0s int c0 = 0; for (int 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 cout << n; return; } // Stores the required sum int mx = 0; // Find the maximum consecutive // length of 0s present in the string int cnt = 0; for (int i = 0; i < n; i++) { if (str[i] == '0') cnt++; else { mx = max(mx, cnt); cnt = 0; } } // Update the overall maximum sum mx = max(mx, cnt); // Find the number of 0s present at // the start and end of the string int 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 = max(mx, cnt); // Print the result cout << mx;}// Driver Codeint main(){ // Given string string s = "1001"; // Store the size of the string int n = s.size(); findMaximumZeros(s, n); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the maximum sum of// consecutive 0s present at the start// and end of any rotation of the string strstatic void findMaximumZeros(String str, int n){ // Stores the count of 0s int c0 = 0; for(int i = 0; i < n; ++i) { if (str.charAt(i) == '0') c0++; } // If the frequency of '1' is 0 if (c0 == n) { // Print n as the result System.out.print(n); return; } // Stores the required sum int mx = 0; // Find the maximum consecutive // length of 0s present in the string int cnt = 0; for(int i = 0; i < n; i++) { if (str.charAt(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 int start = 0, end = n - 1; cnt = 0; // Update the count of 0s at the start while (str.charAt(start) != '1' && start < n) { cnt++; start++; } // Update the count of 0s at the end while (str.charAt(end) != '1' && end >= 0) { cnt++; end--; } // Update the maximum sum mx = Math.max(mx, cnt); // Print the result System.out.println(mx);}// Driver Codepublic static void main (String[] args){ // Given string String s = "1001"; // Store the size of the string int n = s.length(); findMaximumZeros(s, n);}}// This code is contributed by sanjoy_62 |
Python3
# Python3 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 strdef findMaximumZeros(string, n): # Stores the count of 0s c0 = 0 for i in range(n): if (string[i] == '0'): c0 += 1 # If the frequency of '1' is 0 if (c0 == n): # Print n as the result print(n, end = "") return # Stores the required sum mx = 0 # Find the maximum consecutive # length of 0s present in the string cnt = 0 for i in range(n): if (string[i] == '0'): cnt += 1 else: mx = max(mx, cnt) cnt = 0 # Update the overall maximum sum mx = max(mx, cnt) # Find the number of 0s present at # the start and end of the string start = 0 end = n - 1 cnt = 0 # Update the count of 0s at the start while (string[start] != '1' and start < n): cnt += 1 start += 1 # Update the count of 0s at the end while (string[end] != '1' and end >= 0): cnt += 1 end -= 1 # Update the maximum sum mx = max(mx, cnt) # Print the result print(mx, end = "")# Driver Codeif __name__ == "__main__": # Given string s = "1001" # Store the size of the string n = len(s) findMaximumZeros(s, n)# This code is contributed by AnkThon |
C#
// C# program for the above approachusing System;class GFG{// Function to find the maximum sum of// consecutive 0s present at the start// and end of any rotation of the string strstatic void findMaximumZeros(string str, int n){ // Stores the count of 0s int c0 = 0; for(int 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 Console.Write(n); return; } // Stores the required sum int mx = 0; // Find the maximum consecutive // length of 0s present in the string int cnt = 0; for(int 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 int 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 Console.Write(mx);}// Driver Codestatic public void Main (){ // Given string string s = "1001"; // Store the size of the string int n = s.Length; findMaximumZeros(s, n);}}// This code is contributed by avijitmondal1998 |
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 strfunction 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 stringvar n = s.length;findMaximumZeros(s, n); // This code is contributed by SoumikMondal</script> |
Output:
2
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
