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