Tuesday, August 2, 2022
HomeWordPress DevelopmentRely Substrings that may be manufactured from size 1 by changing "01"...

Rely Substrings that may be manufactured from size 1 by changing “01” or “10” with 1 or 0


View Dialogue

Enhance Article

Save Article

Like Article

Given a binary string S of size N, the duty is to search out the variety of pairs of integers [L, R] 1 ≤ L < R ≤ N such that S[L . . . R] (the substring of S from L to R) will be decreased to 1 size string by changing substrings “01” or “10” with “1” and “0” respectively.

Examples:

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

Enter: S = “00000”
Output: 0

 

Strategy: The answer is predicated on the next mathematical concept:

We are able to remedy this primarily based on the exclusion precept. As a substitute of discovering attainable pairs discover the variety of unattainable circumstances and subtract that from all attainable substrings (i.e. N*(N+1)/2 ).

Methods to discover unattainable circumstances?

When s[i] and s[i-1] are identical, then after discount it should both grow to be “00” or “11”. In each circumstances, the substring can’t be decreased to size 1. So substring from 0 to i, from 1 to i, . . . can’t be made to have size 1. That depend of substrings is i.

Comply with the under steps to unravel the issue:

  • Initialize reply ans = N * (N + 1) / 2
  • Run a loop from i = 1 to N – 1
    • If S[i] is the same as S[i – 1], then subtract i from ans.
  • Return ans – N (as a result of there are N substrings having size 1).

Beneath is the implementation of the above method.

C++

  

#embody <bits/stdc++.h>

#outline ll lengthy lengthy

utilizing namespace std;

  

ll discover(string Str)

{

  

    ll n = Str.measurement();

  

    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 essential()

{

    string S = "0110";

  

    

    cout << discover(S) << endl;

    return 0;

}

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

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -
Google search engine

Most Popular

Recent Comments