Maximize non-overlapping Substrings by splitting String into groups with K or (K+1) 1s
Given a binary string S of length N and an integer K, the task is to find the maximum number of non-overlapping substrings that can be obtained by splitting it as per the following conditions:
- Each substring of the string contains K or K+1 number of 1.
- At most consecutive K substrings can contain the same number of 1s
Note: If the string does not contain K or K + 1 number of ones, simply neglect that substring.
Examples:
Input: S = “110101000010011011011011000100000”, K = 2
Output: 6
Explanation: The given string can be split into – [110], [10100], [00100110], [110], [110], [11000100000] so the answer is 6.Input: S = “0000010001001100000110101100110000”, K = 2
Output: 5
Explanation: The given string can be split into – [000001000100], [1100000], [1101], [0110], [0110000] so the answer is 5.Input: S = “11111111111”, K = 4
Output: 2
Explanation: The string can be split into [1111], [1111] and
The remaining string can be neglected because it does not contain K number of 1s.
Approach: This problem can be solved using the Greedy approach is based on the below idea:
To maximize the count of substrings splitting such that as many substring have count of ‘1’ as K.
As it is not possible to split string having same number of ‘1’ successively more than K times, so after splitting K substrings with count of ‘1’ as K, split a substring with count of ‘1’ as K + 1.
Follow the below steps to implement the approach discussed above:
- Iterate the string from i = 0 to N-1:
- Keep adding the characters into the current substring until the count of 1s is K.
- If consecutive K substrings already had the same number of substrings then move forward and add one more 1 into the current substring and start a new substring.
- Increment the count of the number of substrings.
- If it is not possible to have K number of 1s then ignore that substring.
- Return the final count of substrings.
Below is the implementation of the above approach:
C++
// C++ program for above approach #include <bits/stdc++.h> using namespace std; // Function to check the number of 1's // in the given string int check(string s) { int count = 0; for ( int i = 0; i < s.length(); i++) { if (s[i] == '1' ) { count++; } } return count; } // Function to find the minimum operations // to make the array elements same int MaxSplit(string s, int n, int k) { int times = 0; int k2 = 0; int ans = 0; int y; // Traversing the string for ( int i = 0; i < s.length(); i++) { // Creating the substring string x = s.substr(k2, i - k2); // Checking the count of 1's in // the substring y = check(x); // Checking whether the count of 1's // equal to k if (y == k) { // If k successive substring // with count of 1's equals to // k are used then simply find // 1 substring whose count of // 1's is k+1 if (times == k) { continue ; } // Else add 1 to ans as we have // the substring increase times. else { ans += 1; k2 = i; times++; } } // If count of 1's is k+1 then // split the string and add one // to and also set times to zero. else if (y == k + 1) { times = 0; ans += 1; k2 = i; } } // Condition for checking whether // we can take up the remaining string if (y == k && y == k + 1 && y != 0) { ans += 1; } return ans; } // Driver Code int main() { string S = "11111111111" ; int K = 4; int N = S.length(); // Function call cout << MaxSplit(S, N, K); return 0; } |
Java
// Java program for above approach import java.io.*; class GFG { // Function to check the number of 1's // in the given string public static int check(String s) { int count = 0 ; for ( int i = 0 ; i < s.length(); i++) { if (s.charAt(i) == '1' ) { count++; } } return count; } // Function to find the minimum operations // to make the array elements same public static int MaxSplit(String s, int n, int k) { int times = 0 ; int k2 = 0 ; int ans = 0 ; int y = 0 ; // Traversing the string for ( int i = 0 ; i < s.length(); i++) { // Creating the substring String x = s.substring(k2, i); // Checking the count of 1's in // the substring y = check(x); // Checking whether the count of 1's // equal to k if (y == k) { // If k successive substring // with count of 1's equals to // k are used then simply find // 1 substring whose count of // 1's is k+1 if (times == k) { continue ; } // Else add 1 to ans as we have // the substring increase times. else { ans += 1 ; k2 = i; times++; } } // If count of 1's is k+1 then // split the string and add one // to and also set times to zero. else if (y == k + 1 ) { times = 0 ; ans += 1 ; k2 = i; } } // Condition for checking whether // we can take up the remaining string if (y == k && y == k + 1 && y != 0 ) { ans += 1 ; } return ans; } // Driver Code public static void main(String[] args) { String S = "11111111111" ; int K = 4 ; int N = S.length(); // Function call System.out.print(MaxSplit(S, N, K)); } } // This code is contributed by Rohit Pradhan |
Python3
# Python3 program for above approach # Function to check the number of 1's # in the given string def check(s): count = 0 for i in range ( 0 , len (s)): if (s[i] = = '1' ): count + = 1 return count # Function to find the minimum operations # to make the array elements same def MaxSplit(s, n, k): times = 0 k2 = 0 ans = 0 y = 0 # Traversing the string for i in range ( 0 , len (s)): # Creating the substring x = s[k2: k2 + i - k2] # Checking the count of 1's in # the substring y = check(x) # Checking whether the count of 1's # equal to k if (y = = k): # If k successive substring # with count of 1's equals to # k are used then simply find # 1 substring whose count of # 1's is k+1 if (times = = k): continue # Else add 1 to ans as we have # the substring increase times. else : ans + = 1 k2 = i times + = 1 # If count of 1's is k+1 then # split the string and add one # to and also set times to zero. elif (y = = k + 1 ): times = 0 ans + = 1 k2 = i # Condition for checking whether # we can take up the remaining string if (y = = k and y = = k + 1 and y ! = 0 ): ans + = 1 return ans # Driver Code if __name__ = = "__main__" : S = "11111111111" K = 4 N = len (S) # Function call print (MaxSplit(S, N, K)) # This code is contributed by rakeshsahni |
C#
// C# code to implement the approach using System; class GFG { // Function to check the number of 1's // in the given string public static int check(String s) { int count = 0; for ( int i = 0; i < s.Length; i++) { if (s[i] == '1' ) { count++; } } return count; } // Function to find the minimum operations // to make the array elements same public static int MaxSplit(String s, int n, int k) { int times = 0; int k2 = 0; int ans = 0; int y = 0; // Traversing the string for ( int i = 0; i < s.Length; i++) { // Creating the substring String x = s.Substring(k2, i-k2); // Checking the count of 1's in // the substring y = check(x); // Checking whether the count of 1's // equal to k if (y == k) { // If k successive substring // with count of 1's equals to // k are used then simply find // 1 substring whose count of // 1's is k+1 if (times == k) { continue ; } // Else add 1 to ans as we have // the substring increase times. else { ans += 1; k2 = i; times++; } } // If count of 1's is k+1 then // split the string and add one // to and also set times to zero. else if (y == k + 1) { times = 0; ans += 1; k2 = i; } } // Condition for checking whether // we can take up the remaining string if (y == k && y == k + 1 && y != 0) { ans += 1; } return ans; } // Driver Code public static void Main () { String S = "11111111111" ; int K = 4; int N = S.Length; // Function call Console.WriteLine(MaxSplit(S, N, K)); } } // This code is contributed by jana_sayantan. |
Javascript
<script> // JS program for above approach // Function to check the number of 1's // in the given string function check(s) { var count = 0; for ( var i = 0; i < s.length; i++) { if (s[i] == '1 ') { count++; } } return count; } // Function to find the minimum operations // to make the array elements same function MaxSplit(s, n, k) { var times = 0; var k2 = 0; var ans = 0; var y; // Traversing the string for (var i = 0; i < s.length; i++) { // Creating the substring var x = s.substr(k2, i - k2); // Checking the count of 1' s in // the substring y = check(x); // Checking whether the count of 1's // equal to k if (y == k) { // If k successive substring // with count of 1's equals to // k are used then simply find // 1 substring whose count of // 1's is k+1 if (times == k) { continue ; } // Else add 1 to ans as we have // the substring increase times. else { ans += 1; k2 = i; times++; } } // If count of 1's is k+1 then // split the string and add one // to and also set times to zero. else if (y == k + 1) { times = 0; ans += 1; k2 = i; } } // Condition for checking whether // we can take up the remaining string if (y == k && y == k + 1 && y != 0) { ans += 1; } return ans; } // Driver Code var S = "11111111111" ; var K = 4; var N = S.length; // Function call document.write(MaxSplit(S, N, K)); // This code is contributed by phasing17 </script> |
2
Time Complexity: O(N2)
Auxiliary Space: O(1)
Contact Us