Find total number of substrings with 1's greater than 0's, need optimization

Question

Given and string we need to find out the total number of substrings in which 1's are greater than 0's.

I approached this problem using Dynamic programming but I was not able to come up with a solution, I am successful in writing a naive-logic but I was not able to optimize the code (i.e time limit is exceeding)

Any help in optimizing or suggestions for a new approach will be help full. The time complexity of below code is O(n^3) Any solutions to reduce the time-complexity will be helpfull.

Thank in advance.

Code I used:

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main(){
    int tc =0; //total count
    string st; //original string
    getline(cin,st);
    int lent = st.size(); //size of string
    for(int i =0;i<lent;i++){ //loop to generate all possible substrings
        int j = lent-1;
        while(j>=i){
            
            string st1(st.begin()+i,st.end()-j+i); // A substring
            int c1 = count(st1.begin(),st1.end(),'1'); // count of 1's in substring
            if(c1 > st1.size()-c1) tc++; // Condition to check if 1's are more
            j--;
        }
    }
    cout << tc; // Print total substrings
}

Note: A substring is a contiguous sequence of characters within a string. For more information about substrings visit Wikipedia

1 is always greater than 0. Do you mean number of 1s is greater than number of 0s ? — 463035818_is_not_an_ai, Jul 12 '21 at 08:15
This is O(n^3), the counting is O(n) too. Getting O(n^2) shouldn't be that hard. — maraca, Jul 12 '21 at 08:22
@463035818_is_not_a_number Yes total number of 1's in that substring should be greater than total number of 0's in it. — OpOp_1, Jul 12 '21 at 08:22

xskxzr · Accepted Answer · 2021-07-12T14:00:27.977

3

Treat respectively '0' and '1' as integers 1 and -1. Then the string becomes an integer array. Calculate its prefix sum array s, i.e., s[0] = 0 and s[i] = a[0] + ... + a[i - 1]. Now every substring with number of '1's > number of '0's corresponds to a pair (i, j) such that i < j and s[i] > s[j]. You can then use the trick in find total number of (i,j) pairs in array such that i<j and a[i]>a[j]. The time complexity is O(n log n).

edited Jul 12 '21 at 14:00

answered Jul 12 '21 at 12:05

xskxzr

12,442
12
37
77

consider string "10". then which pair (i,j) corresponds to substring "1"? – Patrick Parker Jul 12 '21 at 13:25
@PatrickParker Adding `s[0]=0` (and `s[i]=a[0]+...+a[i-1]`) can fix this issue. – xskxzr Jul 12 '21 at 14:02
@OpOp_1 That's a different problem. – xskxzr Jul 12 '21 at 15:39
@xskxzr Ya, Sorry. – OpOp_1 Jul 12 '21 at 16:45

Patrick Parker · Answer 2 · 2021-07-12T15:39:09.393

0

The problem is you're counting the same chars multiple times from the same start point. You can easily tally the 1's and 0's once from each start point: at the same time as you are traversing the substring. Start at length 0 substring instead of starting at the longest substring.

After this change you will have reduced from O(n^3) to O(n^2) without doing anything unusual or counterintuitive.

"is O(n^2) the most optimized solution" -- no but it's a good first step in improving your algorithm. It can be further optimized.

edited Jul 12 '21 at 15:39

answered Jul 12 '21 at 08:44

Patrick Parker

4,863
4
19
51

This approach reduces the time complexity to O(n^2) by using prefix array, is O(n^2) the most optimized solution, is it possible to attain the time complexity of O(n)? – OpOp_1 Jul 12 '21 at 10:50

Find total number of substrings with 1's greater than 0's, need optimization

2 Answers2