Home > Backend Development > C++ > Find the longest odd parity substring

Find the longest odd parity substring

WBOY
Release: 2023-09-07 16:13:02
forward
597 people have browsed it

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
Copy after login
Output = 6
Copy after login
Copy after login

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
Copy after login
Output = 6
Copy after login
Copy after login

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));
}
Copy after login

Output

The maximum length of the odd parity substring is: 6
Copy after login

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!

source:tutorialspoint.com
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template