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++
// 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
// 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
# 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#
// 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
Javascript
<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 2 )
Espacio Auxiliar: O(1)