Select Page

# Count Substrings that can be made of length 1 by replacing “01” or “10” with 1 or 0

Kashish Kumar
Published: August 2, 2022

Given a binary string S of length N, the task is to find the number of pairs of integers [L, R] 1 ≤ L < R ≤ N such that S[L . . . R] (the substring of S from L to R) can be reduced to 1 length string by replacing substrings “01” or “10” with “1” and “0” respectively.

Examples:

Input: S = “0110”
Output: 4
Explanation: The 4 substrings are 01, 10, 110, 0110.

Input: S = “00000”
Output: 0

Approach: The solution is based on the following mathematical idea:

We can solve this based on the exclusion principle. Instead of finding possible pairs find the number of impossible cases and subtract that from all possible substrings (i.e. N*(N+1)/2 ).

How to find impossible cases?

When s[i] and s[i-1] are same, then after reduction it will either become “00” or “11”. In both cases, the substring cannot be reduced to length 1. So substring from 0 to i, from 1 to i, . . . cannot be made to have length 1. That count of substrings is i.

Follow the below steps to solve the problem:

• Initialize answer ans = N * (N + 1) / 2
• Run a loop from i = 1 to N – 1
• If S[i] is equal to S[i – 1], then subtract i from ans.
• Return ans – N (because there are N substrings having length 1).

Below is the implementation of the above approach.

## C++

 ` ` `#include ``#define ll long long``using` `namespace` `std;`` ` `ll find(string Str)``{`` ` `    ``ll n = Str.size();`` ` `    ``ll ans = n * (n + 1) / 2;`` ` `    ``for` `(ll i = 1; i < n; i++) {``        ``if` `(Str[i] == Str[i - 1])``            ``ans -= i;``    ``}`` ` `    ``return` `ans - n;``}`` ` `int` `main()``{``    ``string S = ``"0110"``;`` ` `    ``    ``cout << find(S) << endl;``    ``return` `0;``}`

Time Complexity: O(N)
Auxiliary Space: O(1)

Source: www.geeksforgeeks.org