Maximum length of segments of 0’s and 1’s

0 0 11 minutes read

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 = 9

Input: 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 zero
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] = 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
int 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 approach
import 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 code
public 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 zero
def 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 Code
if __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 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;
    $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 function
echo find(0, $adj, $n, $dp);
 
// This code is contributed by ihritik
?>

Output

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 zero
int 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 Code
int 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 zero
def 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 code
adj = "100110001010001"
 
# Size of the string
n = len(adj)
 
# Calling the function to find the value
print(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 zero
function 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 code
let adj = "100110001010001";
 
// Size of the string
let n = adj.length;
 
// Calling the function to find the value
console.log(find(adj, n));
 
// THIS CODE IS CONTRIBUTED BY KANCHAN AGARWAL

Output

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 zambiatek!