Given a binary string of length n and an integer k. Consider another string T which is formed by concatenating the given binary string k times. The task is to print the maximum size of a substring of T containing only zeroes.
Examples:
Input: str = 110010, k = 3
Output: 2
str = 110010 T = 110010110010110010(formed after 3 times concatenating str). So, the maximum size of a substring of T(110010110010110010) containing only zeroes is 2.Input: str = 00100110, k = 5
Output: 3
Here, str = 00100110, T = 0010011000100110001001100010011000100110. So, the maximum size of a substring of T containing only zeroes is 3.
A Naive approach is to concatenate K copies of string and traverse through all the elements and count maximum size of substring containing only zeroes.
Efficient Approach:
There is no need to concatenate K copies.
- If string contains only zeroes then the answer is length_of_string * K.
- If string is comprised of both zeroes and ones, then the answer is either the maximum length of a substring of string containing only zeroes, or the sum of the length of the prefix of A containing only zeroes and the length of the suffix of string containing only zeroes.
- One thing to keep note of is that if K=1, then there is no need for prefix and suffix check.
Implementation:
C++
// C++ code to find maximum length// of substring that contains only 0's#include <bits/stdc++.h>using namespace std;// Function to calculate maximum length// of substring containing only zeroint subzero(string str, int k){ int ans = 0, curr = 0; int len = str.length(); // loop to first calculate longest substring // in string for (int i = 0; i < len; ++i) { if (str[i] == '0') curr++; else curr = 0; ans = max(ans, curr); } // if all elements in string are '0' if (ans == len) return len * k; // Else, find size of prefix and // suffix containing only zeroes else { int pre = 0, suff = 0; // Calculate prefix containing only zeroes for (int i = 0; i < len; i++) { if (str[i] == '0') pre++; else break; } // Calculate suffix containing only zeroes for (int i = len - 1; i >= 0; i--) { if (str[i] == '0') suff++; else break; } // if k<=1 then there is no need to take // prefix + suffix into account if (k > 1) ans = max(ans, pre + suff); return ans; }}// Drivers codeint main(){ string str = "00100110"; int k = 5; cout << subzero(str, k); return 0;} |
Java
// Java code to find maximum length// of substring that contains only 0'simport java.io.*;import java.util.*;import java.lang.*;class GfG { // Function to calculate maximum length // of substring containing only zero public static int subzero(String s, int k) { int ans = 0, curr = 0; int len = s.length(); char[] str = s.toCharArray(); // loop to first calculate longest // substring in string for (int i = 0; i < len; ++i) { if (str[i] == '0') curr++; else curr = 0; ans = Math.max(ans, curr); } // if all elements in string are '0' if (ans == len) return len * k; // Else, find size of prefix and // suffix containing only zeroes else { int pre = 0, suff = 0; // Calculate prefix containing // only zeroes for (int i = 0; i < len; i++) { if (str[i] == '0') pre++; else break; } // Calculate suffix containing // only zeroes for (int i = len - 1; i >= 0; i--) { if (str[i] == '0') suff++; else break; } // if k<=1 then there is no need to // take prefix + suffix into account if (k > 1) ans = Math.max(ans, pre + suff); return ans; } } // Drivers code public static void main(String[] args) { String str = "00100110"; int k = 5; System.out.println(subzero(str, k)); }}// This code is contributed by Sagar Shukla |
Python
# Python code calculate maximum length of substring # containing only zero def subzero(str, k): ans = 0 curr = 0 n = len(str) # loop to calculate longest substring in string # containing 0's for i in str: if (i =='0'): curr+= 1 else: curr = 0 ans = max(ans, curr) # if all elements in string a are '0' if (ans == n): print(n * k) return # Else, find prefix and suffix containing # only zeroes else: pre = suff = 0 # Calculate length of the prefix containing # only zeroes for i in str: if(i =='0'): pre+= 1 else: break # Calculate length of the suffix containing # only zeroes for i in range(n-1, -1, -1): if(str[i]=='0'): suff+= 1 else: break # if k<= 1, no need to take suffix + prefix # into account if (k > 1): ans = max(ans, pre + suff) print(ans) return # Driver program to test above functionk = 5str ='00100110'subzero(str, k) |
C#
// C# code to find maximum length// of substring that contains only 0'susing System;class GFG {// Function to calculate maximum length// of substring containing only zeropublic static int subzero(String s, int k){ int ans = 0, curr = 0; int len = s.Length; char[] str = s.ToCharArray(); // loop to first calculate longest // substring in string for (int i = 0; i < len; ++i) { if (str[i] == '0') curr++; else curr = 0; ans = Math.Max(ans, curr); } // if all elements in string are '0' if (ans == len) return len * k; // Else, find size of prefix and // suffix containing only zeroes else { int pre = 0, suff = 0; // Calculate prefix containing // only zeroes for (int i = 0; i < len; i++) { if (str[i] == '0') pre++; else break; } // Calculate suffix containing // only zeroes for (int i = len - 1; i >= 0; i--) { if (str[i] == '0') suff++; else break; } // if k<=1 then there is no need to // take prefix + suffix into account if (k > 1) ans = Math.Max(ans, pre + suff); return ans; }}// Driver codepublic static void Main(){ String str = "00100110"; int k = 5; Console.Write(subzero(str, k));}}// This code is contributed by PrinciRaj1992 |
PHP
<?php // PHP code to find maximum length// of substring that contains only 0's// Function to calculate maximum length// of substring containing only zerofunction subzero($str, $k){ $ans = 0; $curr = 0; $len = strlen($str); // loop to first calculate longest substring // in string for ($i = 0; $i < $len; ++$i) { if ($str[$i] == '0') $curr++; else $curr = 0; $ans = max($ans, $curr); } // if all elements in string are '0' if ($ans == $len) return $len * $k; // Else, find size of prefix and // suffix containing only zeroes else { $pre = 0; $suff = 0; // Calculate prefix containing only zeroes for ($i = 0; $i < $len; $i++) { if ($str[$i] == '0') $pre++; else break; } // Calculate suffix containing only zeroes for ($i = $len - 1; $i >= 0; $i--) { if ($str[$i] == '0') $suff++; else break; } // if k<=1 then there is no need to take // prefix + suffix into account if ($k > 1) $ans = max($ans, $pre + $suff); return $ans; }}// Driver code$str = "00100110";$k = 5;echo subzero($str, $k);// This code is contributed by ita_c?> |
Javascript
<script>// Javascript code to find maximum length// of substring that contains only 0's // Function to calculate maximum length // of substring containing only zero function subzero(s,k) { let ans = 0, curr = 0; let len = s.length; let str = s.split(""); // loop to first calculate longest // substring in string for (let i = 0; i < len; ++i) { if (str[i] == '0') curr++; else curr = 0; ans = Math.max(ans, curr); } // if all elements in string are '0' if (ans == len) return len * k; // Else, find size of prefix and // suffix containing only zeroes else { let pre = 0, suff = 0; // Calculate prefix containing // only zeroes for (let i = 0; i < len; i++) { if (str[i] == '0') pre++; else break; } // Calculate suffix containing // only zeroes for (let i = len - 1; i >= 0; i--) { if (str[i] == '0') suff++; else break; } // if k<=1 then there is no need to // take prefix + suffix into account if (k > 1) ans = Math.max(ans, pre + suff); return ans; } } // Drivers code let str = "00100110"; let k = 5; document.write(subzero(str, k)); // This code is contributed by avanitrachhadiya2155</script> |
Output
3
Complexity Analysis:
- Time Complexity: O(n) as there is a single loop used in the subzero() function.
- Space Complexity: O(1) as there is no extra space used.
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!
