Given a binary string, you can rotate any substring of this string. For Example, let string be denoted by s. Let the first element of string be represented by s[0], second element be represented by s[1] and so on. s = “100110111” Suppose, we rotate the substring starting from s[2] and ending at s[4]. Then the string after this operation will be: Resultant String = “101100111” Now, you are allowed to do at most k operations to rotate any substring. You have to tell the maximum number of contiguous 1 you can make in this string in k or less than k rotations of substring.
Examples:
Input : 100011001 k = 1
Output : 3
Explanation: k is 1, hence you can rotate only once. Rotate the substring starting from s[1] and ending at s[5].
The resultant string will be : 111000001. Hence, maximum contiguous 1 are 3.Input : 001100111000110011100 k = 2
Output : 8
Explanation: k is 2, hence you can rotate twice. Rotate the substring starting at s[6] and ending at s[15].
Resultant string after first rotation : 001100001100011111100.
Then, rotate the substring starting at s[8] and ending at s[12].
Resultant string after second rotation : 001100000001111111100. Hence, maximum number of contiguous 1 are 8.
Concept For Solving:
In order to solve this problem, we will maintain the frequency of 1’s in a portion of contiguous 1’s in the original string in a multiset. Then on each rotation, we will rotate that substring such that, 2 portions of contiguous 1(with maximum frequency) in the string come together. We will do this, by sorting the multiset from greatest to the smallest element.
We will take out the top 2 elements of the multiset and insert their sum back into the multiset. We will continue to do this until k rotations are completed or the number of elements in the multiset is reduced to 1.
Implementation:
CPP
// C++ program to calculate maximum contiguous// ones in string#include <bits/stdc++.h>using namespace std;// function to calculate maximum contiguous onesint maxContiguousOnes(string s, int k){ int i, j, a, b, count; // multiset is used to store frequency of // 1's of each portion of contiguous 1 in // string in decreasing order multiset<int, greater<int> > m; // this loop calculate all the frequency // and stores them in multiset for (i = 0; i < s.length(); i++) { if (s[i] == '1') { count = 0; j = i; while (s[j] == '1' && j < s.length()) { count++; j++; } m.insert(count); i = j - 1; } } // if there is no 1 in string, then return 0 if (m.size() == 0) return 0; // calculates maximum contiguous 1's on // doing rotations while (k > 0 && m.size() != 1) { // Delete largest two elements a = *(m.begin()); m.erase(m.begin()); b = *(m.begin()); m.erase(m.begin()); // insert their sum back into the multiset m.insert(a + b); k--; } // return maximum contiguous ones // possible after k rotations return *(m.begin());}// Driver codeint main(){ string s = "10011110011"; int k = 1; cout << maxContiguousOnes(s, k); return 0;} |
Java
import java.util.Collections;import java.util.TreeSet;public class Main { // function to calculate maximum contiguous ones public static int maxContiguousOnes(String s, int k) { int i, j, a, b, count; TreeSet<Integer> m = new TreeSet<>(Collections.reverseOrder()); // this loop calculate all the frequency // and stores them in TreeSet for (i = 0; i < s.length();) { if (s.charAt(i) == '1') { count = 0; j = i; while (j < s.length() && s.charAt(j) == '1') { count++; j++; } m.add(count); i = j; } else { i++; } } if (m.size() == 0) return 0; while (k > 0 && m.size() != 1) { a = m.first(); m.remove(a); b = m.first(); m.remove(b); m.add(a + b); k--; } return m.first(); } // Driver code public static void main(String[] args) { String s = "10011110011"; int k = 1; System.out.println(maxContiguousOnes(s, k)); }} // this code is contributed by devendrasalunke |
Python
# Python program to calculate maximum contiguous# ones in string# function to calculate maximum contiguous onesdef maxContiguousOnes(s, k): m = [] m.append(0) i = 0 # this loop calculate all the frequency # and stores them in multiset while(i < len(s) and i >= 0): if(s[i] == '1'): count = 0 j = i while(j< len(s) and s[j] == '1'): count += 1 j += 1 m.append(count) m.sort() m.reverse() i = j - 1 i += 1 # if there is no 1 in string, then return 0 if(len(m) == 0): return 0 # calculate maximum contiguous 1's on # doing rotations while(k > 0 and len(m) != 1): # delete largest two elements a = m.pop(0) b = m.pop(0) # insert their sum back into the multiset m.append(a+b) m.sort() m.reverse() k -= 1 # return maximum contiguous ones # possible after k rotations return m.pop(0)# driver program to test above functions = "10011110011"k = 1print(maxContiguousOnes(s, k))# THIS CODE IS CONTRIBUTED BY KIRTI AGARWAL(KIRTIGARWAL23121999) |
C#
using System;using System.Collections.Generic;public class Program{ public static int MaxContiguousOnes(string s, int k){ List<int> m = new List<int>(); m.Add(0); int i = 0; while (i < s.Length && i >= 0){ if (s[i] == '1'){ int count = 0; int j = i; while (j < s.Length && s[j] == '1') { count += 1; j += 1; } m.Add(count); m.Sort(); m.Reverse(); i = j - 1; } i += 1; } if (m.Count == 0){ return 0; } while (k > 0 && m.Count != 1){ int a = m[0]; m.RemoveAt(0); int b = m[0]; m.RemoveAt(0); m.Add(a + b); m.Sort(); m.Reverse(); k -= 1; } return m[0]; } public static void Main(){ string s = "10011110011"; int k = 1; Console.WriteLine(MaxContiguousOnes(s, k)); }} |
Javascript
// JavaScript program to calculate maximum contiguous// ones in string// function to calculate maximum contiguous onesfunction maxContiguousOnes(s, k){ let i, j, a, b, count; // multiset is used to store frequency of // 1's of each portion of contiguous 1 in // string in decreasing order let m = []; m.push(0); // this loop calculate all the frequency // and stores them in multiset for(i = 0; i < s.length; i++){ if(s[i] == '1'){ count = 0; j = i; while(s[j] == '1' && j < s.length){ count++; j++; } m.push(count); m.sort(function(x,y){return x-y;}); m.reverse(); i = j - 1; } } // if there is no 1 in string, them return 0 if(m.length == 0) return 0; //calculates maximum contiguous 1's on // doing rotations while(k > 0 && m.length != 1){ // delete largest two elements a = m.shift(); b = m.shift(); // insert their sum back into the multiset m.push(a+b); m.sort(function(x,y){return x-y;}); m.reverse(); k--; } // return maximum contiguous ones // possible after k rotations return m[0];}// driver programlet s = "10011110011";let k = 1;console.log(maxContiguousOnes(s, k));// THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002) |
6
Time Complexity: O(NlogN) because insert function takes log(N) time to insert in multiset.
Auxiliary Space: O(N) due to multiset data structure.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
