Given a binary string str, the task is to find the maximum length of the sub-string of str that has odd parity. A binary string is said be odd parity if it contains odd number of 1s.
Examples:
Input: str = “1001110”
Output: 6
“001110” is the valid sub-string.Input: str = “101101”
Output: 5
Approach:
- Count the number of 1s in the given string and store it in a variable cnt.
- If cnt = 0 then there is no sub-string possible with odd parity so the result will be 0.
- If cnt is odd then the result will be the complete string.
- Now for the case when cnt is even and > 0, the required sub-string will either start at index 0 and end just before the last occurrence of 1 or start just after the first occurrence of 1 and end at the end of the given string.
- Choose the one with the greater length among the two sub-strings in the previous step.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h>using namespace std; // finds the index of character of string int indexOf(string s, char c, int i) { for(; i < s.length(); i++) if(s[i] == c) return i; return -1; } // finds the last index of character of string int lastIndexOf(string s,char c,int i) { for(; i >= 0; i--) if(s[i] == c) return i; return -1; } // Function to return the maximum // length of the sub-string which // contains odd number of 1s int maxOddParity(string str, int n) { // Find the count of 1s in // the given string int cnt = 0; for (int i = 0; i < n; i++) if (str[i] == '1') cnt++; // If there are only 0s in the string if (cnt == 0) return 0; // If the count of 1s is odd then // the complete string has odd parity if (cnt % 2 == 1) return n; // Index of the first and the second // occurrences of '1' in the string int firstOcc = indexOf(str,'1',0); int secondOcc = indexOf(str,'1', firstOcc + 1); // Index of the last and the second last // occurrences of '1' in the string int lastOcc = lastIndexOf(str,'1',str.length()-1); int secondLastOcc = lastIndexOf(str,'1', lastOcc - 1); // Result will the sub-string ending just // before the last occurrence of '1' or the // sub-string starting just after the first // occurrence of '1' // choose the one with the maximum length return max(lastOcc, n - firstOcc - 1); } // Driver code int main() { string str = "101101"; int n = str.length(); cout<<(maxOddParity(str, n)); } // This code is contributed by Arnab Kundu |
Java
// Java implementation of the approachpublic class GFG { // Function to return the maximum // length of the sub-string which // contains odd number of 1s static int maxOddParity(String str, int n) { // Find the count of 1s in // the given string int cnt = 0; for (int i = 0; i < n; i++) if (str.charAt(i) == '1') cnt++; // If there are only 0s in the string if (cnt == 0) return 0; // If the count of 1s is odd then // the complete string has odd parity if (cnt % 2 == 1) return n; // Index of the first and the second // occurrences of '1' in the string int firstOcc = str.indexOf('1'); int secondOcc = str.indexOf('1', firstOcc + 1); // Index of the last and the second last // occurrences of '1' in the string int lastOcc = str.lastIndexOf('1'); int secondLastOcc = str.lastIndexOf('1', lastOcc - 1); // Result will the sub-string ending just // before the last occurrence of '1' or the // sub-string starting just after the first // occurrence of '1' // choose the one with the maximum length return Math.max(lastOcc, n - firstOcc - 1); } // Driver code public static void main(String[] args) { String str = "101101"; int n = str.length(); System.out.print(maxOddParity(str, n)); }} |
Python3
# Python3 implementation of the approach# Function to return the maximum# length of the sub-string which# contains odd number of 1sdef maxOddParity(string, n): # Find the count of 1s in # the given string cnt = 0 for i in range(n): if string[i] != '1': cnt += 1 # If there are only 0s in the string if cnt == 0: return 0 # If the count of 1s is odd then # the complete string has odd parity if cnt % 2 == 1: return n # Index of the first and the second # occurrences of '1' in the string firstOcc = string.index('1') secondOcc = string.index('1', firstOcc + 1) # Index of the last and the second last # occurrences of '1' in the string lastOcc = string.rindex('1') secondLastOcc = string.rindex('1', 0, lastOcc) # Result will the sub-string ending just # before the last occurrence of '1' or the # sub-string starting just after the first # occurrence of '1' # choose the one with the maximum length return max(lastOcc, n - firstOcc - 1)# Driver Codeif __name__ == "__main__": string = "101101" n = len(string) print(maxOddParity(string, n))# This code is contributed by# sanjeev2552 |
C#
// C# implementation of the above approach using System;class GFG { // Function to return the maximum // length of the sub-string which // contains odd number of 1s static int maxOddParity(String str, int n) { // Find the count of 1s in // the given string int cnt = 0; for (int i = 0; i < n; i++) if (str[i] == '1') cnt++; // If there are only 0s in the string if (cnt == 0) return 0; // If the count of 1s is odd then // the complete string has odd parity if (cnt % 2 == 1) return n; // Index of the first and the second // occurrences of '1' in the string int firstOcc = str.IndexOf('1'); int secondOcc = str.IndexOf('1', firstOcc + 1); // Index of the last and the second last // occurrences of '1' in the string int lastOcc = str.LastIndexOf('1'); int secondLastOcc = str.LastIndexOf('1', lastOcc - 1); // Result will the sub-string ending just // before the last occurrence of '1' or the // sub-string starting just after the first // occurrence of '1' // choose the one with the maximum length return Math.Max(lastOcc, n - firstOcc - 1); } // Driver code public static void Main(String[] args) { String str = "101101"; int n = str.Length; Console.WriteLine(maxOddParity(str, n)); }}/* This code contributed by PrinciRaj1992 */ |
Javascript
<script>// Javascript implementation of the above approach// Function to return the maximum// length of the sub-string which// contains odd number of 1sfunction maxOddParity(str, n){ // Find the count of 1s in // the given string var cnt = 0; for(var i = 0; i < n; i++) if (str[i] == '1') cnt++; // If there are only 0s in the string if (cnt == 0) return 0; // If the count of 1s is odd then // the complete string has odd parity if (cnt % 2 == 1) return n; // Index of the first and the second // occurrences of '1' in the string var firstOcc = str.indexOf('1'); var secondOcc = str.indexOf( '1', firstOcc + 1); // Index of the last and the second last // occurrences of '1' in the string var lastOcc = str.lastIndexOf('1'); var secondLastOcc = str.lastIndexOf( '1', lastOcc - 1); // Result will the sub-string ending just // before the last occurrence of '1' or the // sub-string starting just after the first // occurrence of '1' // choose the one with the maximum length return Math.max(lastOcc, n - firstOcc - 1);}// Driver codevar str = "101101";var n = str.length;document.write(maxOddParity(str, n));// This code is contributed by bunnyram19</script> |
Output
5
Time Complexity: O(n), where n is the length of the string
Auxiliary Space: O(1)
Brute Force:
Approach:
In this approach, we will consider all possible substrings of the given string, and for each substring, we will check if it has odd parity or not. We will keep track of the maximum length substring with odd parity.
- Initialize a variable max_len to 0, which will store the length of the longest odd parity substring.
- Get the length of the input string s.
- Use two nested loops to generate all possible substrings of s. The outer loop iterates through all possible starting indices i, and the inner loop iterates through all possible ending indices j.
- Check if the length of the substring s[i:j] is odd. If it is not odd, skip this substring.
- If the length of the substring is odd, check if its parity is odd by calculating the sum of its digits using the sum() function and checking if it is odd. If it is odd, update max_len to the maximum of its current value and the length of the current substring.
- Return the final value of max_len.
C++
#include <iostream>#include <string>using namespace std;int oddParitySubstring(string s){ int max_len = 0; int n = s.length(); for (int i = 0; i < n; i++) { for (int j = i + 2; j < n + 2; j++) { if ((j - i) % 2 == 1) { string sub_str = s.substr(i, j - i); int sum = 0; for (char c : sub_str) { sum += c - '0'; } if (sum % 2 == 1) { max_len = max(max_len, (int)sub_str.length()); } } } } return max_len;}// example usageint main(){ cout << oddParitySubstring("1001110") << endl; // output: 6 cout << oddParitySubstring("101101") << endl; // output: 5 return 0;} |
Java
// Java Code for above Approachpublic class OddParitySubstring { public static int oddParitySubstring(String s) { int max_len = 0; int n = s.length(); for (int i = 0; i < n; i++) { for (int j = i + 1; j <= n; j++) { String sub_str = s.substring(i, j); int sum = 0; for (char c : sub_str.toCharArray()) { sum += c - '0'; } if (sum % 2 == 1) { max_len = Math.max(max_len, sub_str.length()); } } } return max_len; } public static void main(String[] args) { System.out.println( oddParitySubstring("1001110")); // output: 6 System.out.println( oddParitySubstring("101101")); // output: 5 }} |
Python3
def odd_parity_substring(s): max_len = 0 n = len(s) for i in range(n): for j in range(i+2, n+2): if (j-i) % 2 == 1: sub_str = s[i:j] if sum(int(c) for c in sub_str) % 2 == 1: max_len = max(max_len, len(sub_str)) return max_len# example usageprint(odd_parity_substring("1001110")) # output: 6print(odd_parity_substring("101101")) # output: 5 |
C#
using System;class Program { static int OddParitySubstring(string s) { int maxLen = 0; int n = s.Length; // Iterate over the starting index of the substring for (int i = 0; i < n; i++) { // Iterate over the length of the substring for (int len = 1; len <= n - i; len++) { // Extract the current substring string subStr = s.Substring(i, len); int sum = 0; // Calculate the sum of the binary digits in // the substring foreach(char c in subStr) { sum += c - '0'; } // Check if the sum is odd (odd parity) if (sum % 2 == 1) { maxLen = Math.Max(maxLen, subStr.Length); } } } return maxLen; } // Example usage static void Main(string[] args) { Console.WriteLine( OddParitySubstring("1001110")); // Output: 6 Console.WriteLine( OddParitySubstring("101101")); // Output: 5 }} |
Javascript
// Function to find the maximum length of a substring with odd parityfunction oddParitySubstring(s) { let max_len = 0; // Initialize the maximum length to 0 let n = s.length; // Get the length of the input string for (let i = 0; i < n; i++) { // Iterate over the string characters for (let j = i + 2; j < n + 2; j++) { // Iterate over substring lengths if ((j - i) % 2 === 1) { // Check if the substring length is odd let sub_str = s.substring(i, j); // Extract the substring let sum = 0; // Initialize a sum for calculating parity for (let c of sub_str) { // Iterate over characters in the substring sum += parseInt(c); // Add the character as an integer to the sum } if (sum % 2 === 1) { // Check if the sum of the substring is odd max_len = Math.max(max_len, sub_str.length); // Update max_len if the current substring is longer } } } } return max_len; // Return the maximum length with odd parity}// Example usageconsole.log(oddParitySubstring("1001110")); // Output: 6console.log(oddParitySubstring("101101")); // Output: 5 |
Output
6 5
Time Complexity: O(n^3)
Space Complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
