Given a string comprising of ones and zeros. The task is to find the maximum length of the segments of string such that a number of 1 in each segment is greater than 0.
Note: Each segment taken should be distinct. Index starts from 0.
Examples:
Input: str = “100110001010001”
Output: 9
First segment from index 0 to 4 (10011), total length = 5
Second segment from index 8 to 10 (101), total length = 3
Third segment from index 14 till 14 (1), total length = 1,
Hence answer is 5 + 3 + 1 = 9Input: str = “0010111101100000”
Output: 13
The maximum length can be formed by taking segment
from index 0 till index 12 (0010111101100),
i.e. of total length = 13
Approach:
- If start == n, limiting condition arises, return 0.
- Run a loop from start till n, computing for each subarray till n.
- If character is 1 then increment the count of 1 else increment the count of 0.
- If count of 1 is greater than 0, recursively call the function for index (k+1) i.e. next index and add the remaining length i.e. k-start+1.
- Else only recursively call the function for next index k+1.
- Return dp[start].
Below is the implementation of above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Recursive Function to find total length of the array// Where 1 is greater than zeroint find(int start, string adj, int n, int dp[]){ // If reaches till end if (start == n) return 0; // If dp is saved if (dp[start] != -1) return dp[start]; dp[start] = 0; int one = 0, zero = 0, k; // Finding for each length for (k = start; k < n; k++) { // If the character scanned is 1 if (adj[k] == '1') one++; else zero++; // If one is greater than zero, add total // length scanned till now if (one > zero) dp[start] = max(dp[start], find(k + 1, adj, n, dp) + k - start + 1); // Continue with next length else dp[start] = max(dp[start], find(k + 1, adj, n, dp)); } // Return the value for start index return dp[start];}// Driver Codeint main(){ string adj = "100110001010001"; // Size of string int n = adj.size(); int dp[n + 1]; memset(dp, -1, sizeof(dp)); // Calling the function to find the value of function cout << find(0, adj, n, dp) << endl; return 0;} |
Java
// Java implementation of// above approachimport java.util.*;import java.lang.Math;class GFG{// Recursive Function to find // total length of the array // Where 1 is greater than zero public static int find(int start, String adj, int n, int dp[]){ // If reaches till end if (start == n) return 0; // If dp is saved if (dp[start] != -1) return dp[start]; dp[start] = 0; int one = 0, zero = 0, k; // Finding for each length for (k = start; k < n; k++) { // If the character scanned is 1 if (adj.charAt(k) == '1') one++; else zero++; // If one is greater than // zero, add total length // scanned till now if (one > zero) dp[start] = Math.max(dp[start], find(k + 1, adj, n, dp) + k - start + 1); // Continue with next length else dp[start] = Math.max(dp[start], find(k + 1, adj, n, dp)); } return dp[start];}// Driver codepublic static void main (String[] args) { String adj = "100110001010001"; // Size of string int n = adj.length(); int dp[] = new int[n + 1]; Arrays.fill(dp, -1); // Calling the function to find // the value of function System.out.println(find(0, adj, n, dp));}}// This code is contributed // by Kirti_Mangal |
Python3
# Python 3 implementation of above approach# Recursive Function to find total length # of the array where 1 is greater than zerodef find(start, adj, n, dp): # If reaches till end if (start == n): return 0 # If dp is saved if (dp[start] != -1): return dp[start] dp[start] = 0 one = 0 zero = 0 # Finding for each length for k in range(start, n, 1): # If the character scanned is 1 if (adj[k] == '1'): one += 1 else: zero += 1 # If one is greater than zero, add # total length scanned till now if (one > zero): dp[start] = max(dp[start], find(k + 1, adj, n, dp) + k - start + 1) # Continue with next length else: dp[start] = max(dp[start], find(k + 1, adj, n, dp)) # Return the value for start index return dp[start]# Driver Codeif __name__ == '__main__': adj = "100110001010001" # Size of string n = len(adj) dp = [-1 for i in range(n + 1)] # Calling the function to find the # value of function print(find(0, adj, n, dp))# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of above approach using System; class GFG { // Recursive Function to find total length of the array // Where 1 is greater than zero public static int find(int start, string adj, int n, int[] dp) { // If reaches till end if (start == n) return 0; // If dp is saved if (dp[start] != -1) return dp[start]; dp[start] = 0; int one = 0, zero = 0, k; // Finding for each length for (k = start; k < n; k++) { // If the character scanned is 1 if (adj[k] == '1') one++; else zero++; // If one is greater than zero, add total // length scanned till now if (one > zero) dp[start] = Math.Max(dp[start], find(k + 1, adj, n, dp) + k - start + 1); // Continue with next length else dp[start] = Math.Max(dp[start], find(k + 1, adj, n, dp)); } // Return the value for start index return dp[start]; } // Driver Code static void Main() { string adj = "100110001010001"; // Size of string int n = adj.Length; int[] dp = new int[n + 1]; for(int i = 0; i <= n; i++) dp[i] = -1; // Calling the function to find the value of function Console.Write(find(0, adj, n, dp) + "\n"); } //This code is contributed by DrRoot_} |
Javascript
<script>// javascript implementation of// above approach // Recursive Function to find // total length of the array // Where 1 is greater than zero function find(start, adj , n , dp) { // If reaches till end if (start == n) return 0; // If dp is saved if (dp[start] != -1) return dp[start]; dp[start] = 0; var one = 0, zero = 0, k; // Finding for each length for (k = start; k < n; k++) { // If the character scanned is 1 if (adj[k] == '1') one++; else zero++; // If one is greater than // zero, add total length // scanned till now if (one > zero) dp[start] = Math.max(dp[start], find(k + 1, adj, n, dp) + k - start + 1); // Continue with next length else dp[start] = Math.max(dp[start], find(k + 1, adj, n, dp)); } return dp[start]; } // Driver code var adj = "100110001010001"; // Size of string var n = adj.length; var dp = Array(n + 1).fill(-1); // Calling the function to find // the value of function document.write(find(0, adj, n, dp));// This code is contributed by umadevi9616 </script> |
PHP
<?php// PHP implementation of above approach// Recursive Function to find total length // of the array where 1 is greater than zerofunction find($start, $adj, $n, $dp){ // If reaches till end if ($start == $n) return 0; // If $dp is saved if ($dp[$start] != -1) return $dp[$start]; $dp[$start] = 0; $one = 0; $zero = 0; // Finding for each length for ($k = $start; $k < $n; $k++) { // If the character scanned is 1 if ($adj[$k] == '1') $one++; else $zero++; // If one is greater than zero, add total // length scanned till now if ($one > $zero) $dp[$start] = max($dp[$start], find($k + 1, $adj, $n, $dp) + $k - $start + 1); // Continue with next length else $dp[$start] = max($dp[$start], find($k + 1, $adj, $n, $dp)); } // Return the value for $start index return $dp[$start];}// Driver Code$adj = "100110001010001";// Size of string$n = strlen($adj);$dp = array_fill(0, $n + 1, -1);// Calling the function // to find the value of functionecho find(0, $adj, $n, $dp);// This code is contributed by ihritik?> |
Output
9
Another approach : Using DP Tabulation method ( Iterative approach )
The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.
Implementation :
C++
#include <bits/stdc++.h>using namespace std;// Function to find total length of the array// Where 1 is greater than zeroint find(string adj, int n){ // dp array to store the maximum length of the array // where 1 is greater than zero int dp[n + 1]; // Initialize dp array for (int i = 0; i <= n; i++) { dp[i] = 0; } // Find the maximum length of the array // where 1 is greater than zero for (int i = 0; i < n; i++) { int one = 0, zero = 0; // Find for each length for (int j = i; j < n; j++) { // If the character scanned is 1 if (adj[j] == '1') one++; else zero++; // If one is greater than zero, add total // length scanned till now if (one > zero) dp[j + 1] = max(dp[j + 1], dp[i] + j - i + 1); // Continue with next length else dp[j + 1] = max(dp[j + 1], dp[i]); } } // Return the maximum length of the array return dp[n];}// Driver Codeint main(){ string adj = "100110001010001"; // Size of string int n = adj.size(); // Calling the function to find the value of function cout << find(adj, n) << endl; return 0;} |
Java
import java.util.*;public class Main { // Function to find the total length of the array // where 1 is greater than zero static int find(String adj, int n) { // dp array to store the maximum length of the array // where 1 is greater than zero int[] dp = new int[n + 1]; // Initialize dp array for (int i = 0; i <= n; i++) { dp[i] = 0; } // Find the maximum length of the array // where 1 is greater than zero for (int i = 0; i < n; i++) { int one = 0, zero = 0; // Find for each length for (int j = i; j < n; j++) { // If the character scanned is 1 if (adj.charAt(j) == '1') one++; else zero++; // If one is greater than zero, add the // total length scanned till now if (one > zero) dp[j + 1] = Math.max(dp[j + 1], dp[i] + j - i + 1); // Continue with the next length else dp[j + 1] = Math.max(dp[j + 1], dp[i]); } } // Return the maximum length of the array return dp[n]; } // Driver Code public static void main(String[] args) { String adj = "100110001010001"; // Size of the string int n = adj.length(); // Calling the function to find the value of the // function System.out.println(find(adj, n)); }}// This code is contributed by shivamgupta310570 |
Python3
# Function to find the total length of the array# where 1 is greater than zerodef find(adj, n): # Array to store the maximum length of the array # where 1 is greater than zero dp = [0] * (n + 1) # Find the maximum length of the array # where 1 is greater than zero for i in range(n): one = 0 zero = 0 # Find for each length for j in range(i, n): # If the character scanned is 1 if adj[j] == '1': one += 1 else: zero += 1 # If one is greater than zero, add the total # length scanned so far if one > zero: dp[j + 1] = max(dp[j + 1], dp[i] + j - i + 1) # Continue with the next length else: dp[j + 1] = max(dp[j + 1], dp[i]) # Return the maximum length of the array return dp[n]# Driver codeadj = "100110001010001"# Size of the stringn = len(adj)# Calling the function to find the valueprint(find(adj, n))# THIS CODE IS CONTRIBUTED BY KANCHAN AGARWAL |
C#
using System;public class GFG { // Function to find total length of the array // Where 1 is greater than zero static int Find(string adj, int n) { // dp array to store the maximum length of the array // where 1 is greater than zero int[] dp = new int[n + 1]; // Initialize dp array for (int i = 0; i <= n; i++) { dp[i] = 0; } // Find the maximum length of the array // where 1 is greater than zero for (int i = 0; i < n; i++) { int one = 0, zero = 0; // Find for each length for (int j = i; j < n; j++) { // If the character scanned is 1 if (adj[j] == '1') one++; else zero++; // If one is greater than zero, add total // length scanned till now if (one > zero) dp[j + 1] = Math.Max(dp[j + 1], dp[i] + j - i + 1); else dp[j + 1] = Math.Max(dp[j + 1], dp[i]); } } // Return the maximum length of the array return dp[n]; } // Driver Code static void Main(string[] args) { string adj = "100110001010001"; // Size of string int n = adj.Length; // Calling the function to find the value of function Console.WriteLine(Find(adj, n)); }} |
Javascript
// Function to find the total length of the array// where 1 is greater than zerofunction find(adj, n) { // Array to store the maximum length of the array // where 1 is greater than zero let dp = new Array(n + 1).fill(0); // Find the maximum length of the array // where 1 is greater than zero for (let i = 0; i < n; i++) { let one = 0, zero = 0; // Find for each length for (let j = i; j < n; j++) { // If the character scanned is 1 if (adj[j] === '1') one++; else zero++; // If one is greater than zero, add the total // length scanned so far if (one > zero) dp[j + 1] = Math.max(dp[j + 1], dp[i] + j - i + 1); // Continue with the next length else dp[j + 1] = Math.max(dp[j + 1], dp[i]); } } // Return the maximum length of the array return dp[n];}// Driver codelet adj = "100110001010001";// Size of the stringlet n = adj.length;// Calling the function to find the valueconsole.log(find(adj, n));// THIS CODE IS CONTRIBUTED BY KANCHAN AGARWAL |
Output
9
Time Complexity: O(N^2)
Auxiliary Space: O(N)
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!
