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

user_16429860 0
Viewed 1028

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

substring time-complexity optimization algorithm c++
2 Answers

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).

user_53767890

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.

user_70982590
Related