La permutación lexicográficamente más pequeña de una string que se puede reducir a la longitud K eliminando los prefijos de longitud K de las substrings palindrómicas de longitud 2K

Dada una string binaria str de longitud N y un entero K , la tarea es encontrar la permutación lexicográficamente más pequeña de la string str que se puede reducir a la longitud K eliminando cada prefijo de longitud K de las substrings palindrómicas de longitud 2K . Si no existe tal permutación, imprima » No es posible «.

Ejemplos:

Entrada: str = “0000100001100001”, K = 4
Salida: 0001100000011000
Explicación: En la string “0001100000011000”, cada substring de 2K de longitud se convierte en un palíndromo cada vez que se elimina un prefijo de longitud K, hasta que la longitud de la string se reduce a K.

Entrada: str = “100111”, K = 2
Salida: “No es posible”

Enfoque: siga los pasos a continuación para resolver el problema:

• Cuente el número de 0 s y 1 s presentes en la string . Si la cuenta de 0 s o 1 s es un múltiplo de N / K, entonces es posible la reducción K de la string. De lo contrario, imprima «No es posible «.
• Inicialice una string tempStr para almacenar la string de 2K de longitud lexicográficamente más pequeña formada inicialmente .
• Inicialice una string finalStr para almacenar la string resultante que satisfaga las condiciones dadas.
• Distribuya los 0 en un segmento de longitud 2K de acuerdo con la siguiente fórmula:
  • Número de ceros en la substring de longitud 2K, N0 = ((Número de ceros en la string de longitud N)/(Longitud total de la string))*(2K)
  • Número de unos en la substring de longitud de 2K, N1 = (2*K – Número de ceros en la substring de longitud de 2K)
• Agregue tempStr con 0s N0/2 veces y con 1s N1/2 veces y nuevamente con 0s N0/2 veces.
• Agregue tempStr (N/2K) veces a finalStr e inserte (N%2K) caracteres de tempStr al final de finalStr .
• Imprime finalStr como la string resultante. 
   

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 count the number of
// zeroes present in the string
int count_zeroes(int n, string str)
{
    int cnt = 0;
 
    // Traverse the string
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '0')
            cnt++;
    }
 
    // Return the count
    return cnt;
}
 
// Function to rearrange the string s.t
// the string can be reduced to a length
// K as per the given rules
string kReducingStringUtil(
    int n, int k, string str,
    int no_of_zeroes)
{
 
    // Distribute the count of 0s and
    // 1s in segment of length 2k
    int zeroes_in_2k = ((no_of_zeroes)
                        * (2 * k))
                       / n;
 
    int ones_in_2k = 2 * k - zeroes_in_2k;
 
    // Store string that are initially
    // have formed lexicographically
    // smallest 2k length substring
    string temp_str = "";
 
    for (int i = 0;
         i < (zeroes_in_2k) / 2; i++) {
        temp_str.push_back('0');
    }
    for (int i = 0; i < ones_in_2k; i++) {
        temp_str.push_back('1');
    }
    for (int i = 0;
         i < (zeroes_in_2k) / 2; i++) {
        temp_str.push_back('0');
    }
 
    // Store the lexicographically
    // smallest string of length n
    // that satisfy the condition
    string final_str = "";
 
    // Insert temp_str into final_str
    // (n/2k) times and add (n%2k)
    // characters of temp_str at end
    for (int i = 0;
         i < n / (2 * k); i++) {
        final_str += (temp_str);
    }
 
    for (int i = 0;
         i < n % (2 * k); i++) {
        final_str.push_back(temp_str[i]);
    }
 
    // Return the final string
    return final_str;
}
 
// Function to reduce the string to
// length K that follows the given
// conditions
string kReducingString(int n, int k,
                       string str)
{
    // If the string contains either
    // 0s or 1s then it always be
    // reduced into a K length string
    int no_of_zeroes = count_zeroes(n, str);
 
    int no_of_ones = n - no_of_zeroes;
 
    // If the string contains only 0s
    // 1s then it always reduces to
    // a K length string
    if (no_of_zeroes == 0
        || no_of_zeroes == n) {
        return str;
    }
 
    // If K = 1
    if (k == 1) {
        if (no_of_zeroes == 0
            || no_of_zeroes == n) {
            return str;
        }
        else {
            return "Not Possible";
        }
    }
 
    // Check whether the given string
    // is K reducing string or not
    bool check = 0;
 
    for (int i = (n / k);
         i < n; i += (n / k)) {
 
        if (no_of_zeroes == i
            || no_of_ones == i) {
            check = 1;
            break;
        }
    }
 
    if (check == 0) {
        return "Not Possible";
    }
 
    // Otherwise recursively find
    // the string
    return kReducingStringUtil(n, k,
                               str,
                               no_of_zeroes);
}
 
// Driver Code
int main()
{
    string str = "0000100001100001";
    int K = 4;
    int N = str.length();
 
    // Function Call
    cout << kReducingString(N, K, str);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG{
 
// Function to count the number of
// zeroes present in the string
static int count_zeroes(int n, String str)
{
    int cnt = 0;
     
    // Traverse the string
    for(int i = 0; i < str.length(); i++)
    {
        if (str.charAt(i) == '0')
            cnt++;
    }
 
    // Return the count
    return cnt;
}
 
// Function to rearrange the string s.t
// the string can be reduced to a length
// K as per the given rules
static String kReducingStringUtil(int n, int k,
                                  String str,
                                  int no_of_zeroes)
{
     
    // Distribute the count of 0s and
    // 1s in segment of length 2k
    int zeroes_in_2k = ((no_of_zeroes) *
                        (2 * k)) / n;
 
    int ones_in_2k = 2 * k - zeroes_in_2k;
 
    // Store string that are initially
    // have formed lexicographically
    // smallest 2k length substring
    String temp_str = "";
 
    for(int i = 0; i < (zeroes_in_2k) / 2; i++)
    {
        temp_str += '0';
    }
    for(int i = 0; i < ones_in_2k; i++)
    {
        temp_str += '1';
    }
    for(int i = 0; i < (zeroes_in_2k) / 2; i++)
    {
        temp_str += '0';
    }
     
    // Store the lexicographically
    // smallest string of length n
    // that satisfy the condition
    String final_str = "";
 
    // Insert temp_str into final_str
    // (n/2k) times and add (n%2k)
    // characters of temp_str at end
    for(int i = 0; i < n / (2 * k); i++)
    {
        final_str += (temp_str);
    }
 
    for(int i = 0; i < n % (2 * k); i++)
    {
        final_str += temp_str.charAt(i);
    }
 
    // Return the final string
    return final_str;
}
 
// Function to reduce the string to
// length K that follows the given
// conditions
static String kReducingString(int n, int k,
                              String str)
{
     
    // If the string contains either
    // 0s or 1s then it always be
    // reduced into a K length string
    int no_of_zeroes = count_zeroes(n, str);
 
    int no_of_ones = n - no_of_zeroes;
 
    // If the string contains only 0s
    // 1s then it always reduces to
    // a K length string
    if (no_of_zeroes == 0 ||
        no_of_zeroes == n)
    {
        return str;
    }
 
    // If K = 1
    if (k == 1)
    {
        if (no_of_zeroes == 0 ||
            no_of_zeroes == n)
        {
            return str;
        }
        else
        {
            return "Not Possible";
        }
    }
 
    // Check whether the given string
    // is K reducing string or not
    boolean check = false;
 
    for(int i = (n / k); i < n; i += (n / k))
    {
        if (no_of_zeroes == i ||
            no_of_ones == i)
        {
            check = true;
            break;
        }
    }
 
    if (check == false)
    {
        return "Not Possible";
    }
 
    // Otherwise recursively find
    // the string
    return kReducingStringUtil(n, k, str,
                               no_of_zeroes);
}
 
// Driver Code
public static void main(String[] args)
{
    String str = "0000100001100001";
    int K = 4;
    int N = str.length();
 
    // Function Call
    System.out.println(kReducingString(N, K, str));
}
}
 
// This code is contributed by akhilsaini

# Python3 program for the above approach
 
# Function to count the number of
# zeroes present in the string
def count_zeroes(n, str):
   
  cnt = 0
 
  # Traverse the string
  for i in range(0, len(str)):
    if (str[i] == '0'):
      cnt += 1
       
  # Return the count
  return cnt
 
# Function to rearrange the string s.t
# the string can be reduced to a length
# K as per the given rules
def kReducingStringUtil(n, k, str,
                        no_of_zeroes):
   
  # Distribute the count of 0s and
  # 1s in segment of length 2k
  zeroes_in_2k = (((no_of_zeroes) *
                   (2 * k)) // n)
 
  ones_in_2k = 2 * k - zeroes_in_2k
 
  # Store string that are initially
  # have formed lexicographically
  # smallest 2k length substring
  temp_str = ""
 
  for i in range(0, (zeroes_in_2k) // 2):
    temp_str += '0'
     
  for i in range(0, (ones_in_2k)):
    temp_str += '1'
   
  for i in range(0, (zeroes_in_2k) // 2):
    temp_str += '0'
     
  # Store the lexicographically
  # smallest string of length n
  # that satisfy the condition
  final_str = ""
 
  # Insert temp_str into final_str
  # (n/2k) times and add (n%2k)
  # characters of temp_str at end
  for i in range(0, n // (2 * k)):
    final_str += (temp_str)
 
  for i in range(0, n % (2 * k)):
    final_str += (temp_str[i])
     
  # Return the final string
  return final_str
 
# Function to reduce the string to
# length K that follows the given
# conditions
def kReducingString(n, k, str):
   
  # If the string contains either
  # 0s or 1s then it always be
  # reduced into a K length string
  no_of_zeroes = count_zeroes(n, str)
 
  no_of_ones = n - no_of_zeroes
 
  # If the string contains only 0s
  # 1s then it always reduces to
  # a K length string
  if (no_of_zeroes == 0 or
      no_of_zeroes == n):
    return str
 
  # If K = 1
  if (k == 1):
    if (no_of_zeroes == 0 or
        no_of_zeroes == n):
      return str
    else:
      return "Not Possible"
     
  # Check whether the given string
  # is K reducing string or not
  check = 0
 
  for i in range((n // k), n, (n // k)):
    if (no_of_zeroes == i or no_of_ones == i):
      check = 1
      break
       
  if (check == 0):
    return "Not Possible"
 
  # Otherwise recursively find
  # the string
  return kReducingStringUtil(n, k, str,
                             no_of_zeroes)
 
# Driver Code
if __name__ == '__main__':
   
  str = "0000100001100001"
  K = 4;
  N = len(str)
 
  # Function Call
  print(kReducingString(N, K, str))
   
# This code is contributed by akhilsaini

// C# program for the above approach
using System;
 
class GFG{
 
// Function to count the number of
// zeroes present in the string
static int count_zeroes(int n, string str)
{
    int cnt = 0;
 
    // Traverse the string
    for(int i = 0; i < str.Length; i++)
    {
        if (str[i] == '0')
            cnt++;
    }
 
    // Return the count
    return cnt;
}
 
// Function to rearrange the string s.t
// the string can be reduced to a length
// K as per the given rules
static string kReducingStringUtil(int n, int k,
                                  string str,
                                  int no_of_zeroes)
{
     
    // Distribute the count of 0s and
    // 1s in segment of length 2k
    int zeroes_in_2k = ((no_of_zeroes) *
                        (2 * k)) / n;
 
    int ones_in_2k = 2 * k - zeroes_in_2k;
 
    // Store string that are initially
    // have formed lexicographically
    // smallest 2k length substring
    string temp_str = "";
 
    for(int i = 0; i < (zeroes_in_2k) / 2; i++)
    {
        temp_str += '0';
    }
    for(int i = 0; i < ones_in_2k; i++)
    {
        temp_str += '1';
    }
    for(int i = 0; i < (zeroes_in_2k) / 2; i++)
    {
        temp_str += '0';
    }
 
    // Store the lexicographically
    // smallest string of length n
    // that satisfy the condition
    string final_str = "";
 
    // Insert temp_str into final_str
    // (n/2k) times and add (n%2k)
    // characters of temp_str at end
    for(int i = 0; i < n / (2 * k); i++)
    {
        final_str += (temp_str);
    }
 
    for(int i = 0; i < n % (2 * k); i++)
    {
        final_str += temp_str[i];
    }
 
    // Return the final string
    return final_str;
}
 
// Function to reduce the string to
// length K that follows the given
// conditions
static string kReducingString(int n, int k,
                              string str)
{
     
    // If the string contains either
    // 0s or 1s then it always be
    // reduced into a K length string
    int no_of_zeroes = count_zeroes(n, str);
 
    int no_of_ones = n - no_of_zeroes;
 
    // If the string contains only 0s
    // 1s then it always reduces to
    // a K length string
    if (no_of_zeroes == 0 ||
        no_of_zeroes == n)
    {
        return str;
    }
 
    // If K = 1
    if (k == 1)
    {
        if (no_of_zeroes == 0 ||
            no_of_zeroes == n)
        {
            return str;
        }
        else
        {
            return "Not Possible";
        }
    }
 
    // Check whether the given string
    // is K reducing string or not
    bool check = false;
 
    for(int i = (n / k); i < n; i += (n / k))
    {
        if (no_of_zeroes == i ||
            no_of_ones == i)
        {
            check = true;
            break;
        }
    }
 
    if (check == false)
    {
        return "Not Possible";
    }
 
    // Otherwise recursively find
    // the string
    return kReducingStringUtil(n, k, str,
                               no_of_zeroes);
}
 
// Driver Code
public static void Main()
{
    string str = "0000100001100001";
    int K = 4;
    int N = str.Length;
 
    // Function Call
    Console.WriteLine(kReducingString(N, K, str));
}
}
 
// This code is contributed by akhilsaini

<script>
 
      // JavaScript program for the above approach
      // Function to count the number of
      // zeroes present in the string
      function count_zeroes(n, str) {
        var cnt = 0;
 
        // Traverse the string
        for (var i = 0; i < str.length; i++)
        {
          if (str[i] === "0") cnt++;
        }
 
        // Return the count
        return cnt;
      }
 
      // Function to rearrange the string s.t
      // the string can be reduced to a length
      // K as per the given rules
      function kReducingStringUtil(n, k, str, no_of_zeroes)
      {
        // Distribute the count of 0s and
        // 1s in segment of length 2k
        var zeroes_in_2k =
        parseInt((no_of_zeroes * (2 * k)) / n);
 
        var ones_in_2k = 2 * k - zeroes_in_2k;
 
        // Store string that are initially
        // have formed lexicographically
        // smallest 2k length substring
        var temp_str = "";
 
        for (var i = 0; i < zeroes_in_2k / 2; i++)
        {
          temp_str += "0";
        }
        for (var i = 0; i < ones_in_2k; i++)
        {
          temp_str += "1";
        }
        for (var i = 0; i < zeroes_in_2k / 2; i++)
        {
          temp_str += "0";
        }
 
        // Store the lexicographically
        // smallest string of length n
        // that satisfy the condition
        var final_str = "";
 
        // Insert temp_str into final_str
        // (n/2k) times and add (n%2k)
        // characters of temp_str at end
        for (var i = 0; i < n / (2 * k); i++)
        {
          final_str += temp_str;
        }
 
        for (var i = 0; i < n % (2 * k); i++)
        {
          final_str += temp_str[i];
        }
 
        // Return the final string
        return final_str;
      }
 
      // Function to reduce the string to
      // length K that follows the given
      // conditions
      function kReducingString(n, k, str)
      {
        // If the string contains either
        // 0s or 1s then it always be
        // reduced into a K length string
        var no_of_zeroes = count_zeroes(n, str);
 
        var no_of_ones = n - no_of_zeroes;
 
        // If the string contains only 0s
        // 1s then it always reduces to
        // a K length string
        if (no_of_zeroes === 0 || no_of_zeroes === n)
        {
          return str;
        }
 
        // If K = 1
        if (k === 1) {
          if (no_of_zeroes === 0 || no_of_zeroes === n)
          {
            return str;
          } else {
            return "Not Possible";
          }
        }
 
        // Check whether the given string
        // is K reducing string or not
        var check = false;
 
        for (var i = n / k; i < n; i += n / k) {
          if (no_of_zeroes === i || no_of_ones === i)
          {
            check = true;
            break;
          }
        }
 
        if (check === false) {
          return "Not Possible";
        }
 
        // Otherwise recursively find
        // the string
        return kReducingStringUtil(n, k, str, no_of_zeroes);
      }
 
      // Driver Code
      var str = "0000100001100001";
      var K = 4;
      var N = str.length;
 
      // Function Call
      document.write(kReducingString(N, K, str));
       
</script>

0001100000011000

Complejidad temporal: O(N)
Espacio auxiliar: O(N)