# Longest substring with count of 1s more than 0s

Given a binary string find the longest substring which contains 1’s more than 0’s.**Examples:**

Input : 1010 Output : 3 Substring 101 has 1 occurring more number of times than 0. Input : 101100 Output : 5 Substring 10110 has 1 occurring more number of times than 0.

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

A **simple** solution is to one by one consider all the substrings and check if that substring has a count of 1 more than 0. If the count is more than comparing its length with maximum length substring found till now. The time complexity of this solution is O(n^2).

An **efficient** solution is to use hashing. The idea is to find the sum of string traversed until now. Add 1 to the result if the current character is ‘1’ else subtract 1. Now the problem reduces to finding the largest subarray having a sum greater than zero. To find the largest subarray having a sum greater than zero, we check the value of the sum. If sum is greater than zero, then the largest subarray with a sum greater than zero is arr[0..i]. If the sum is less than zero, then find the size of subarray arr[j+1..i], where j is index up to which sum of subarray arr[0..j] is sum -1 and j < i and compare that size with largest subarray size found so far. To find index j, store values of sum for arr[0..j] in hash table for all 0 <= j <= i. There might be a possibility that a given value of sum repeats. In that case store only first index for which that sum is obtained as it is required to get the length of largest subarray and that is obtained from first index occurrence.

Below is the implementation of above approach:

## C++

`// CPP program to find largest substring` `// having count of 1s more than count` `// count of 0s.` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Function to find longest substring` `// having count of 1s more than count` `// of 0s.` `int` `findLongestSub(string bin)` `{` ` ` `int` `n = bin.length(), i;` ` ` `// To store sum.` ` ` `int` `sum = 0;` ` ` `// To store first occurrence of each` ` ` `// sum value.` ` ` `unordered_map<` `int` `, ` `int` `> prevSum;` ` ` `// To store maximum length.` ` ` `int` `maxlen = 0;` ` ` `// To store current substring length.` ` ` `int` `currlen;` ` ` `for` `(i = 0; i < n; i++) {` ` ` `// Add 1 if current character is 1` ` ` `// else subtract 1.` ` ` `if` `(bin[i] == ` `'1'` `)` ` ` `sum++;` ` ` `else` ` ` `sum--;` ` ` `// If sum is positive, then maximum` ` ` `// length substring is bin[0..i]` ` ` `if` `(sum > 0) {` ` ` `maxlen = i + 1;` ` ` `}` ` ` `// If sum is negative, then maximum` ` ` `// length substring is bin[j+1..i], where` ` ` `// sum of substring bin[0..j] is sum-1.` ` ` `else` `if` `(sum <= 0) {` ` ` `if` `(prevSum.find(sum - 1) != prevSum.end()) {` ` ` `currlen = i - prevSum[sum - 1];` ` ` `maxlen = max(maxlen, currlen);` ` ` `}` ` ` `}` ` ` `// Make entry for this sum value in hash` ` ` `// table if this value is not present.` ` ` `if` `(prevSum.find(sum) == prevSum.end())` ` ` `prevSum[sum] = i;` ` ` `}` ` ` `return` `maxlen;` `}` `// Driver code` `int` `main()` `{` ` ` `string bin = ` `"1010"` `;` ` ` `cout << findLongestSub(bin);` ` ` `return` `0;` `}` |

## Java

`// Java program to find largest substring` `// having count of 1s more than count` `// count of 0s.` `import` `java.util.HashMap;` `class` `GFG` `{` ` ` `// Function to find longest substring` ` ` `// having count of 1s more than count` ` ` `// of 0s.` ` ` `static` `int` `findLongestSub(String bin)` ` ` `{` ` ` `int` `n = bin.length(), i;` ` ` `// To store sum.` ` ` `int` `sum = ` `0` `;` ` ` `// To store first occurrence of each` ` ` `// sum value.` ` ` `HashMap<Integer,` ` ` `Integer> prevSum = ` `new` `HashMap<>();` ` ` `// To store maximum length.` ` ` `int` `maxlen = ` `0` `;` ` ` `// To store current substring length.` ` ` `int` `currlen;` ` ` `for` `(i = ` `0` `; i < n; i++)` ` ` `{` ` ` `// Add 1 if current character is 1` ` ` `// else subtract 1.` ` ` `if` `(bin.charAt(i) == ` `'1'` `)` ` ` `sum++;` ` ` `else` ` ` `sum--;` ` ` `// If sum is positive, then maximum` ` ` `// length substring is bin[0..i]` ` ` `if` `(sum > ` `0` `)` ` ` `{` ` ` `maxlen = i + ` `1` `;` ` ` `}` ` ` `// If sum is negative, then maximum` ` ` `// length substring is bin[j+1..i], where` ` ` `// sum of substring bin[0..j] is sum-1.` ` ` `else` `if` `(sum <= ` `0` `)` ` ` ` ` `{` ` ` `if` `(prevSum.containsKey(sum - ` `1` `))` ` ` `{` ` ` `currlen = i - (prevSum.get(sum - ` `1` `) == ` `null` `? ` `1` `:` ` ` `prevSum.get(sum - ` `1` `));` ` ` `maxlen = Math.max(maxlen, currlen);` ` ` `}` ` ` `}` ` ` `// Make entry for this sum value in hash` ` ` `// table if this value is not present.` ` ` `if` `(!prevSum.containsKey(sum))` ` ` `prevSum.put(sum, i);` ` ` `}` ` ` `return` `maxlen;` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `String bin = ` `"1010"` `;` ` ` `System.out.println(findLongestSub(bin));` ` ` `}` `}` `// This code is contributed by` `// sanjeev2552` |

## Python3

`# Python 3 program to find largest substring` `# having count of 1s more than count` `# count of 0s.` `# Function to find longest substring` `# having count of 1s more than count` `# of 0s.` `def` `findLongestSub(bin1):` ` ` `n ` `=` `len` `(bin1)` ` ` `# To store sum.` ` ` `sum` `=` `0` ` ` `# To store first occurrence of each` ` ` `# sum value.` ` ` `prevSum ` `=` `{i:` `0` `for` `i ` `in` `range` `(n)}` ` ` `# To store maximum length.` ` ` `maxlen ` `=` `0` ` ` `# To store current substring length.` ` ` `for` `i ` `in` `range` `(n):` ` ` ` ` `# Add 1 if current character is 1` ` ` `# else subtract 1.` ` ` `if` `(bin1[i] ` `=` `=` `'1'` `):` ` ` `sum` `+` `=` `1` ` ` `else` `:` ` ` `sum` `-` `=` `1` ` ` `# If sum is positive, then maximum` ` ` `# length substring is bin1[0..i]` ` ` `if` `(` `sum` `> ` `0` `):` ` ` `maxlen ` `=` `i ` `+` `1` ` ` `# If sum is negative, then maximum` ` ` `# length substring is bin1[j+1..i], where` ` ` `# sum of substring bin1[0..j] is sum-1.` ` ` `elif` `(` `sum` `<` `=` `0` `):` ` ` `if` `((` `sum` `-` `1` `) ` `in` `prevSum):` ` ` `currlen ` `=` `i ` `-` `prevSum[` `sum` `-` `1` `]` ` ` `maxlen ` `=` `max` `(maxlen, currlen)` ` ` ` ` `# Make entry for this sum value in hash` ` ` `# table if this value is not present.` ` ` `if` `((` `sum` `) ` `not` `in` `prevSum):` ` ` `prevSum[` `sum` `] ` `=` `i` ` ` `return` `maxlen` `# Driver code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `bin1 ` `=` `"1010"` ` ` `print` `(findLongestSub(bin1))` `# This code is contributed by` `# Surendra_Gangwar` |

## C#

`// C# program to find largest substring` `// having count of 1s more than count` `// count of 0s.` `using` `System;` `using` `System.Collections.Generic;` `class` `GFG` `{` ` ` `// Function to find longest substring` ` ` `// having count of 1s more than count` ` ` `// of 0s.` ` ` `static` `int` `findLongestSub(String bin)` ` ` `{` ` ` `int` `n = bin.Length, i;` ` ` `// To store sum.` ` ` `int` `sum = 0;` ` ` `// To store first occurrence of each` ` ` `// sum value.` ` ` `Dictionary<` `int` `,` ` ` `int` `> prevSum = ` `new` `Dictionary<` `int` `,` ` ` `int` `>();` ` ` `// To store maximum length.` ` ` `int` `maxlen = 0;` ` ` `// To store current substring length.` ` ` `int` `currlen;` ` ` `for` `(i = 0; i < n; i++)` ` ` `{` ` ` `// Add 1 if current character is 1` ` ` `// else subtract 1.` ` ` `if` `(bin[i] == ` `'1'` `)` ` ` `sum++;` ` ` `else` ` ` `sum--;` ` ` `// If sum is positive, then maximum` ` ` `// length substring is bin[0..i]` ` ` `if` `(sum > 0)` ` ` `{` ` ` `maxlen = i + 1;` ` ` `}` ` ` `// If sum is negative, then maximum` ` ` `// length substring is bin[j+1..i], where` ` ` `// sum of substring bin[0..j] is sum-1.` ` ` `else` `if` `(sum <= 0)` ` ` ` ` `{` ` ` `if` `(prevSum.ContainsKey(sum - 1))` ` ` `{` ` ` `currlen = i - (prevSum[sum - 1] == 0 ? 1 :` ` ` `prevSum[sum - 1]);` ` ` `maxlen = Math.Max(maxlen, currlen);` ` ` `}` ` ` `}` ` ` `// Make entry for this sum value in hash` ` ` `// table if this value is not present.` ` ` `if` `(!prevSum.ContainsKey(sum))` ` ` `prevSum.Add(sum, i);` ` ` `}` ` ` `return` `maxlen;` ` ` `}` ` ` `// Driver code` ` ` `public` `static` `void` `Main(String[] args)` ` ` `{` ` ` `String bin = ` `"1010"` `;` ` ` `Console.WriteLine(findLongestSub(bin));` ` ` `}` `}` `// This code is contributed by 29AjayKumar` |

## Javascript

`<script>` `// Javascript program to find largest substring` `// having count of 1s more than count` `// count of 0s.` `// Function to find longest substring` ` ` `// having count of 1s more than count` ` ` `// of 0s.` `function` `findLongestSub(bin)` `{` ` ` `let n = bin.length, i;` ` ` ` ` `// To store sum.` ` ` `let sum = 0;` ` ` ` ` `// To store first occurrence of each` ` ` `// sum value.` ` ` `let prevSum = ` `new` `Map();` ` ` ` ` `// To store maximum length.` ` ` `let maxlen = 0;` ` ` ` ` `// To store current substring length.` ` ` `let currlen;` ` ` `for` `(i = 0; i < n; i++)` ` ` `{` ` ` ` ` `// Add 1 if current character is 1` ` ` `// else subtract 1.` ` ` `if` `(bin[i] == ` `'1'` `)` ` ` `sum++;` ` ` `else` ` ` `sum--;` ` ` ` ` `// If sum is positive, then maximum` ` ` `// length substring is bin[0..i]` ` ` `if` `(sum > 0)` ` ` `{` ` ` `maxlen = i + 1;` ` ` `}` ` ` ` ` `// If sum is negative, then maximum` ` ` `// length substring is bin[j+1..i], where` ` ` `// sum of substring bin[0..j] is sum-1.` ` ` `else` `if` `(sum <= 0)` ` ` ` ` `{` ` ` `if` `(prevSum.has(sum - 1))` ` ` `{` ` ` `currlen = i - (prevSum.get(sum - 1) == ` `null` `? 1 :` ` ` `prevSum.get(sum - 1));` ` ` `maxlen = Math.max(maxlen, currlen);` ` ` `}` ` ` `}` ` ` ` ` `// Make entry for this sum value in hash` ` ` `// table if this value is not present.` ` ` `if` `(!prevSum.has(sum))` ` ` `prevSum.set(sum, i);` ` ` `}` ` ` `return` `maxlen;` `}` `// Driver code` `let bin = ` `"1010"` `;` `document.write(findLongestSub(bin));` `// This code is contributed by rag2127` `</script>` |

**Output:**

3

**Time Complexity: **O(n) **Auxiliary Space: **O(n)