Find the longest odd parity substring

Introduction

In this tutorial, we develop a method to find the maximum length of an odd-even substring. Odd parity in a substring means that 1 is repeated an odd number of times in the string. Parity in C defines the bit set number and is 1 in numbers. There are two types of parity: even parity and odd parity.

When the total number of "1"s in the binary representation is an odd number, it is called an odd parity string. In this tutorial, we use C programming concepts to find the maximum length odd parity substring.

Implementation 1

String = 101100

Output = 6

In the above example, the length of the maximum odd-parity substring is 6, and the substring can be 011100. The total number of 1's in this substring is 3, which is an odd number. Make it an odd parity substring.

Implementation 2

String = 1011010

Output = 6

In the above example, the maximum length of the odd parity substring in the given string is 6. A possible substring could be 011010 since it contains a total of 3 "1"s, making it an odd-parity substring.

algorithm

• Create a counter variable ct to count the 1's in the input string.

• If ct = 0, the odd parity substring cannot be formed because the input string only contains 0.

• If the total number of 1's in the input string is an odd number, the length of the substring is equal to the length of the string.

• When the value of the ct variable is an even number, the substring can be composed of two possibilities.

• Find the longest odd parity substring.

• Print length.

Example

We implement Example 2 in C and use the length() function of the string class to find the length of the input string and the resulting substring.

#include <bits/stdc++.h>
using namespace std;
 
// user defined function for calculating the index value of string
int indexOfString(string st, char ch, int j){
   for(; j < st.length(); j++)
      if(st[j] == ch)
      return j;      
      return -1;
}
//finding the lsat index value of the string
int lastIndexOfString(string st,char ch,int j){
   for(; j >= 0; j--)
      if(st[j] == ch)
   return j;
   return -1;
}
 
//user defined function to find the length of the longest odd parity substring
int maxSubstring(string s, int l){

   //variable for counting 1s
   int ct = 0;
   for (int j = 0; j < l; j++)
      if (s[j] == '1')
         ct++;

   //different counter variable conditions
   if (ct == 0)
      return 0;
       
   if (ct % 2 == 1)
      return l;
       
   int firstTime = indexOfString(s,'1',0);
   int secondTime = indexOfString(s,'1', firstTime + 1);

   int lastTime = lastIndexOfString(s,'1',s.length()-1);
   int secondLastTime = lastIndexOfString(s,'1', lastTime - 1);

   return max(lastTime, l - firstTime - 1);
}

// Controller
int main(){
   string s = "1011010";
   int l = s.length();
   cout<<"The maximum length of the odd parity substring is:" <<(maxSubstring(s, l));
}

Output

The maximum length of the odd parity substring is: 6

in conclusion

In this tutorial, we develop a method to find the length of the longest odd-even substring from a given input string. The length of the odd parity substring is calculated using a counter variable and defining different if conditions for it.

We use the length() function of the string class to help find the length of the substring and the index value of the input string. The index value generates the substring.

The above is the detailed content of Find the longest odd parity substring. For more information, please follow other related articles on the PHP Chinese website!