Given a binary string str of length N, the task is to count the maximum number of adjacent pairs of form “01” or “10” that can be formed from the given binary string when one character can be considered for only one pair.
Note: Adjacent pair means pair formed using adjacent characters.
Examples:
Input: str = “0101110”
Output: 3
Explanation: The three pairs are “01” at the starting first,
“01” starting at 2nd index (0 based indexing)
and “10” at the end of the string.
Notice 2 pairs can also be formed by using “10” from index 1 and “10” at last.
But that does not give the maximum number of adjacent pairs.Input: str = “0011”
Output: 1Input: str = “11”
Output: 0
Approach: This is a implementation based problem. Follow the steps mentioned here to solve the problem:
- Traverse string from left to right.
- Initialize count of pairs with 0 and consider the previous character as free.
- Run a loop from 1 to size of the string.
- Check if the previous character is opposite to the current character or not and also if it is free or not
- If yes then increment count of pairs and set the character as not free.
- Else continue the traversal in the loop considering the character as free.
- Print the count of pairs.
Below is the implementation of the above approach.
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Count pairs functionvoid check_pairs(string str){ // Initialize pairs with 0 int pairs = 0; // Previous char is free to pair bool prev_c = true; // Traverse string from second position for (int i = 1; i < str.size(); i++) { // Check both char are opposite or not // and also check previous char // is free or not if (str[i] != str[i - 1] && prev_c) { // Once previous char paired // with other make it false prev_c = false; // Increment pairs count pairs++; } else { // Previous char is free for pair prev_c = true; } } // Print count of pairs of two characters cout << pairs;}// Driver Codeint main(){ string str = "0101110"; // Function call check_pairs(str); return 0;} |
Java
// Java code to implement the above approachclass GFG { // Count pairs function static void check_pairs(String str) { // Initialize pairs with 0 int pairs = 0; // Previous char is free to pair boolean prev_c = true; // Traverse String from second position for (int i = 1; i < str.length(); i++) { // Check both char are opposite or not // and also check previous char // is free or not if (str.charAt(i) != str.charAt(i - 1) && prev_c) { // Once previous char paired // with other make it false prev_c = false; // Increment pairs count pairs++; } else { // Previous char is free for pair prev_c = true; } } // Print count of pairs of two characters System.out.println(pairs); } // Driver Code public static void main(String args[]) { String str = "0101110"; // Function call check_pairs(str); }}// This code is contributed by gfgking |
Python3
# python3 code to implement the above approach# Count pairs functiondef check_pairs(str): # Initialize pairs with 0 pairs = 0 # Previous char is free to pair prev_c = True # Traverse string from second position for i in range(1, len(str)): # Check both char are opposite or not # and also check previous char # is free or not if (str[i] != str[i - 1] and prev_c): # Once previous char paired # with other make it false prev_c = False # Increment pairs count pairs += 1 else: # Previous char is free for pair prev_c = True # Print count of pairs of two characters print(pairs)# Driver Codeif __name__ == "__main__": str = "0101110" # Function call check_pairs(str)# This code is contributed by rakeshsahni |
C#
// C# code to implement the above approachusing System;class GFG { // Count pairs function static void check_pairs(string str) { // Initialize pairs with 0 int pairs = 0; // Previous char is free to pair bool prev_c = true; // Traverse string from second position for (int i = 1; i < str.Length; i++) { // Check both char are opposite or not // and also check previous char // is free or not if (str[i] != str[i - 1] && prev_c) { // Once previous char paired // with other make it false prev_c = false; // Increment pairs count pairs++; } else { // Previous char is free for pair prev_c = true; } } // Print count of pairs of two characters Console.Write(pairs); } // Driver Code public static int Main() { string str = "0101110"; // Function call check_pairs(str); return 0; }}// This code is contributed by Taranpreet |
Javascript
<script> // JavaScript code for the above approach // Count pairs function function check_pairs(str) { // Initialize pairs with 0 let pairs = 0; // Previous char is free to pair let prev_c = true; // Traverse string from second position for (let i = 1; i < str.length; i++) { // Check both char are opposite or not // and also check previous char // is free or not if (str[i] != str[i - 1] && prev_c) { // Once previous char paired // with other make it false prev_c = false; // Increment pairs count pairs++; } else { // Previous char is free for pair prev_c = true; } } // Print count of pairs of two characters document.write(pairs); } // Driver Code let str = "0101110"; // Function call check_pairs(str); // This code is contributed by Potta Lokesh </script> |
Output
3
Time Complexity: O(N)
Auxiliary Space: 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!
Share your thoughts in the comments
