La string lexicográficamente más grande posible al invertir las substrings que tienen un número par de 1

Dada una string binaria S , la tarea es convertir la string S dada a su forma lexicográfica máxima invirtiendo las substrings que tienen un número par de 1s .

Ejemplos:

Entrada: S = “10101”
Salida: 11010
Explicación:
Invertir la substring {S[0], …, S[2]} modifica S a “10101”. 
Invertir la substring {S[1], …, S[4]} modifica S a “11010”. 
Ahora, no se puede elegir ninguna otra substring, ya que cada una tendrá un número impar de 1 o será lexicográficamente más pequeña que la string anterior. Por lo tanto, 11010 es la string lexicográficamente más grande que se puede realizar.

Entrada: S = “0101”
Salida: 1010

Enfoque: la idea es comenzar desde el primer índice y recorrer la string hasta que el número total de 1 en la string sea par. Tan pronto como se encuentre un índice donde haya exactamente un número par de 1 , invierta la string desde el índice inicial hasta el índice final. Repita este proceso para cada índice para obtener la string lexicográficamente más grande.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the lexicographically
// maximum string by reversing substrings
// having even numbers of 1s
void lexicographicallyMax(string s)
{
    // Store size of string
    int n = s.size();
 
    // Traverse the string
    for (int i = 0; i < n; i++) {
 
        // Count the number of 1s
        int count = 0;
 
        // Stores the starting index
        int beg = i;
 
        // Stores the end index
        int end = i;
 
        // Increment count, when 1
        // is encountered
        if (s[i] == '1')
            count++;
 
        // Traverse the remaining string
        for (int j = i + 1; j < n; j++) {
            if (s[j] == '1')
                count++;
 
            if (count % 2 == 0
                && count != 0) {
                end = j;
                break;
            }
        }
 
        // Reverse the string from
        // starting and end index
        reverse(s.begin() + beg,
                s.begin() + end + 1);
    }
 
    // Printing the string
    cout << s << "\n";
}
 
// Driver Code
int main()
{
    string S = "0101";
    lexicographicallyMax(S);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function to find the lexicographically
// maximum string by reversing substrings
// having even numbers of 1s
static void lexicographicallyMax(String s)
{
     
    // Store size of string
    int n = s.length();
     
    // Traverse the string
    for(int i = 0; i < n; i++)
    {
         
        // Count the number of 1s
        int count = 0;
         
        // Stores the starting index
        int beg = i;
 
        // Stores the end index
        int end = i;
 
        // Increment count, when 1
        // is encountered
        if (s.charAt(i) == '1')
            count++;
             
        // Traverse the remaining string
        for(int j = i + 1; j < n; j++)
        {
            if (s.charAt(j) == '1')
                count++;
 
            if (count % 2 == 0 &&
                count != 0)
            {
                end = j;
                break;
            }
        }
         
        // Reverse the string from
        // starting and end index
        s = reverse(s, beg, end + 1);
    }
     
    // Printing the string
   System.out.println(s);
}
 
static String reverse(String s, int beg, int end)
{
    StringBuilder x = new StringBuilder("");
     
    for(int i = 0; i < beg; i++)
        x.append(s.charAt(i));
    for(int i = end - 1; i >= beg; i--)
        x.append(s.charAt(i));
    for(int i = end; i < s.length(); i++)
        x.append(s.charAt(i));
 
    return x.toString();
}
 
// Driver Code
public static void main(String args[])
{
    String S = "0101";
     
    lexicographicallyMax(S);
}
}
 
// This code is contributed by jyoti369

# Python3 program for the above approach
 
# Function to find the lexicographically
# maximum string by reversing substrings
# having even numbers of 1s
def lexicographicallyMax(s):
     
    # Store size of string
    n = len(s)
     
    # Traverse the string
    for i in range(n):
         
        # Count the number of 1s
        count = 0
 
        # Stores the starting index
        beg = i
 
        # Stores the end index
        end = i
         
        # Increment count, when 1
        # is encountered
        if (s[i] == '1'):
            count += 1
 
        # Traverse the remaining string
        for j in range(i + 1, n):
            if (s[j] == '1'):
                count += 1
                 
            if (count % 2 == 0 and count != 0):
                end = j
                break
                 
        # temp is for Reverse the string from
        # starting and end index
        temp = s[beg : end + 1]
        temp = temp[::-1]
        s = s[0 : beg] + temp + s[end + 1 :]
         
    # Printing the string
    print(s)
 
# Driver Code
S = "0101"
 
lexicographicallyMax(S)
 
# This code is contributed by avanitrachhadiya2155

// C# program for the above approach
using System;
using System.Text;
class GFG
{
     
// Function to find the lexicographically
// maximum string by reversing substrings
// having even numbers of 1s
static void lexicographicallyMax(String s)
{
     
    // Store size of string
    int n = s.Length;
     
    // Traverse the string
    for(int i = 0; i < n; i++)
    {
         
        // Count the number of 1s
        int count = 0;
         
        // Stores the starting index
        int beg = i;
 
        // Stores the end index
        int end = i;
 
        // Increment count, when 1
        // is encountered
        if (s[i] == '1')
            count++;
             
        // Traverse the remaining string
        for(int j = i + 1; j < n; j++)
        {
            if (s[j] == '1')
                count++;
            if (count % 2 == 0 &&
                count != 0)
            {
                end = j;
                break;
            }
        }
         
        // Reverse the string from
        // starting and end index
        s = reverse(s, beg, end + 1);
    }
     
    // Printing the string
   Console.WriteLine(s);
}
 
static String reverse(String s, int beg, int end)
{
    StringBuilder x = new StringBuilder("");
     
    for(int i = 0; i < beg; i++)
        x.Append(s[i]);
    for(int i = end - 1; i >= beg; i--)
        x.Append(s[i]);
    for(int i = end; i < s.Length; i++)
        x.Append(s[i]);
 
    return x.ToString();
}
 
// Driver Code
public static void Main(String []args)
{
    String S = "0101";
    lexicographicallyMax(S);
}
}
 
 
// This code is contributed by Princi Singh

<script>
 
// JavaScript program for the above approach
 
// Function to find the lexicographically
// maximum string by reversing substrings
// having even numbers of 1s
function lexicographicallyMax(s)
{
    // Store size of string
    var n = s.length;
 
    // Traverse the string
    for (var i = 0; i < n; i++) {
 
        // Count the number of 1s
        var count = 0;
 
        // Stores the starting index
        var beg = i;
 
        // Stores the end index
        var end = i;
 
        // Increment count, when 1
        // is encountered
        if (s[i] == '1')
            count++;
 
        // Traverse the remaining string
        for (var j = i + 1; j < n; j++) {
            if (s[j] == '1')
                count++;
 
            if (count % 2 == 0
                && count != 0) {
                end = j;
                break;
            }
        }
 
        // Reverse the string from
        // starting and end index
        for(var i = beg; i<parseInt((end+1)/2);i++)
        {
            let temp = s[i] ;
            s[i] = s[end - i+1] ;
            s[end -i+1 ] = temp;
        }
    }
 
    // Printing the string
    document.write( s.join("") + "<br>");
}
 
// Driver Code
var S = "0101".split('');
lexicographicallyMax(S);
 
</script>

1010

Complejidad de Tiempo: O(N ² )
Espacio Auxiliar: O(1)