Given a binary string, count number of substrings that start and end with 1. - GeeksforGeeks
Difficulty Level: Rookie We strongly recommend to minimize your browser and try this yourself first. A Simple Solution is to run two loops. Outer loops picks every 1 as starting point and inner loop searches for ending 1 and increments count whenever it finds 1. // A simple C++ program to count number of substrings starting and ending // with 1 #include
using namespace std; int countSubStr(char str[]) { int res = 0; // Initialize result // Pick a starting point for (int i=0; str[i] !='\0'; i++) { if (str[i] == '1') { // Search for all possible ending point for (int j=i+1; str[j] !='\0'; j++) if (str[j] == '1') res++; } } return res; } // Driver program to test above function int main() { char str[] = "00100101"; cout << countSubStr(str); return 0; } Output: 3 Time Complexity of the above solution is O(n2). We can find count in O(n) using a single traversal of input string. Following are steps. a) Count the number of 1's. Let the count of 1's be m.
Read full article from Given a binary string, count number of substrings that start and end with 1. - GeeksforGeeks
