Reorganizar la string de modo que ningún par de caracteres adyacentes sean del mismo tipo

Dada la string alfanumérica str , la tarea es reorganizar la string de modo que no haya dos caracteres adyacentes del mismo tipo, es decir, que dos caracteres adyacentes no puedan ser letras o dígitos. Si tal arreglo no es posible, imprima -1 .

Ejemplos:

Entrada: str = «geeks2020»
Salida: g2e0e2k0s

Entrada: str = “IPL20”
Salida: I2P0L

Enfoque ingenuo: el enfoque más simple es generar todas las permutaciones posibles de la string dada y, para cada permutación, verificar si satisface las condiciones dadas o no. Si resulta ser verdadero para cualquier permutación, imprima esa permutación. Si no existe tal permutación, imprima -1 .

Complejidad temporal: O(2 ^N )
Espacio auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es almacenar todos los alfabetos y los dígitos por separado y reorganizarlos colocándolos alternativamente en la string resultante. Si el conteo de los alfabetos y los dígitos difieren en más de 1, imprima -1 ya que no es posible el arreglo deseado.

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

// C++ program to implement
// the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to rearrange given
// alphanumeric string such that
// no two adjacent characters
// are of the same type
string rearrange(string s)
{
    // Stores alphabets and digits
    string s1 = "", s2 = "";
 
    // Store the alphabets and digits
    // separately in the strings
    for (char x : s) {
        isalpha(x) ? s1.push_back(x)
                   : s2.push_back(x);
    }
 
    // Stores the count of
    // alphabets and digits
    int n = s1.size();
    int m = s2.size();
 
    // If respective counts
    // differ by 1
    if (abs(n - m) > 1)
 
        // Desired arrangement
        // not possible
        return "-1";
 
    // Stores the indexes
    int i = 0, j = 0, k = 0;
 
    // Check if first character
    // should be alphabet or digit
    int flag = (n >= m) ? 1 : 0;
 
    // Place alphabets and digits
    // alternatively
    while (i < n and j < m) {
 
        // If current character
        // needs to be alphabet
        if (flag)
            s[k++] = s1[i++];
 
        // If current character
        // needs to be a digit
        else
            s[k++] = s2[j++];
 
        // Flip flag for alternate
        // arrangement
        flag = !flag;
    }
 
    // Return resultant string
    return s;
}
 
// Driver Code
int main()
{
    // Given String
    string str = "geeks2020";
 
    // Function Call
    cout << rearrange(str) << endl;
 
    return 0;
}

// Java program to implement
// the above approach
class GFG{
 
// Function to rearrange given
// alphanumeric String such that
// no two adjacent characters
// are of the same type
static String rearrange(String s)
{
  // Stores alphabets and digits
  String s1 = "", s2 = "", ans = "";
  char []s3 = s.toCharArray();
 
  // Store the alphabets and digits
  // separately in the Strings
  for (char x : s3)
  {
    if(x >= 'a' && x <= 'z')
      s1 += x ;
    else
      s2 += x;
  }
 
  // Stores the count of
  // alphabets and digits
  int n = s1.length();
  int m = s2.length();
 
  // If respective counts
  // differ by 1
  if (Math.abs(n - m) > 1)
 
    // Desired arrangement
    // not possible
    return "-1";
 
  // Stores the indexes
  int i = 0, j = 0, k = 0;
 
  // Check if first character
  // should be alphabet or digit
  int flag = (n >= m) ? 1 : 0;
 
  // Place alphabets and digits
  // alternatively
  while (i < n && j < m)
  {
    // If current character
    // needs to be alphabet
    if (flag != 0)
      ans += s1.charAt(i++);
 
    // If current character
    // needs to be a digit
    else
      ans += s2.charAt(j++);
 
    // Flip flag for alternate
    // arrangement
    if(flag == 1)
      flag = 0;
    else
      flag = 1;
  }
 
  // Return resultant String
  return ans;
}
 
// Driver Code
public static void main(String[] args)
{
  // Given String
  String str = "geeks2020";
 
  // Function Call
  System.out.print(rearrange(str) + "\n");
}
}
 
// This code is contributed by gauravrajput1

# Python3 program to implement
# the above approach
 
# Function to rearrange given
# alphanumeric such that no
# two adjacent characters
# are of the same type
def rearrange(s):
     
    # Stores alphabets and digits
    s1 = []
    s2 = []
 
    # Store the alphabets and digits
    # separately in the strings
    for x in s:
        if x.isalpha():
            s1.append(x)
        else:
            s2.append(x)
 
    # Stores the count of
    # alphabets and digits
    n = len(s1)
    m = len(s2)
 
    # If respective counts
    # differ by 1
    if (abs(n - m) > 1):
 
        # Desired arrangement
        # not possible
        return "-1"
 
    # Stores the indexes
    i = 0
    j = 0
    k = 0
 
    # Check if first character
    # should be alphabet or digit
    flag = 0
    if (n >= m):
        flag = 1
    else:
        flag = 0
 
    # Place alphabets and digits
    # alternatively
    while (i < n and j < m):
 
        # If current character
        # needs to be alphabet
        if (flag):
            s[k] = s1[i]
            k += 1
            i += 1
 
        # If current character
        # needs to be a digit
        else:
            s[k] = s2[j]
            k += 1
            j += 1
 
        # Flip flag for alternate
        # arrangement
        flag = not flag
 
    # Return resultant string
    return "".join(s)
 
# Driver Code
if __name__ == '__main__':
     
    # Given String
    str = "geeks2020"
 
    str1 = [i for i in str]
 
    # Function call
    print(rearrange(str1))
 
# This code is contributed by mohit kumar 29

// C# program to implement
// the above approach
using System;
class GFG{
 
// Function to rearrange given
// alphanumeric String such that
// no two adjacent characters
// are of the same type
static String rearrange(String s)
{
  // Stores alphabets and digits
  String s1 = "", s2 = "", ans = "";
  char []s3 = s.ToCharArray();
 
  // Store the alphabets and digits
  // separately in the Strings
  foreach (char x in s3)
  {
    if(x >= 'a' && x <= 'z')
      s1 += x ;
    else
      s2 += x;
  }
 
  // Stores the count of
  // alphabets and digits
  int n = s1.Length;
  int m = s2.Length;
 
  // If respective counts
  // differ by 1
  if (Math.Abs(n - m) > 1)
 
    // Desired arrangement
    // not possible
    return "-1";
 
  // Stores the indexes
  int i = 0, j = 0, k = 0;
 
  // Check if first character
  // should be alphabet or digit
  int flag = (n >= m) ? 1 : 0;
 
  // Place alphabets and digits
  // alternatively
  while (i < n && j < m)
  {
    // If current character
    // needs to be alphabet
    if (flag != 0)
      ans += s1[i++];
 
    // If current character
    // needs to be a digit
    else
      ans += s2[j++];
 
    // Flip flag for alternate
    // arrangement
    if(flag == 1)
      flag = 0;
    else
      flag = 1;
  }
 
  // Return resultant String
  return ans;
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given String
  String str = "geeks2020";
 
  // Function Call
  Console.Write(rearrange(str) + "\n");
}
}
 
// This code is contributed by 29AjayKumar

<script>
// Javascript program to implement
// the above approach
 
// Function to rearrange given
// alphanumeric String such that
// no two adjacent characters
// are of the same type
function rearrange(s)
{
 
    // Stores alphabets and digits
  let s1 = "", s2 = "", ans = "";
  let s3 = s.split("");
  
  // Store the alphabets and digits
  // separately in the Strings
  for (let x = 0; x < s3.length; x++)
  {
    if(s3[x] >= 'a' && s3[x] <= 'z')
      s1 += s3[x] ;
    else
      s2 += s3[x];
  }
  
  // Stores the count of
  // alphabets and digits
  let n = s1.length;
  let m = s2.length;
  
  // If respective counts
  // differ by 1
  if (Math.abs(n - m) > 1)
  
    // Desired arrangement
    // not possible
    return "-1";
  
  // Stores the indexes
  let i = 0, j = 0, k = 0;
  
  // Check if first character
  // should be alphabet or digit
  let flag = (n >= m) ? 1 : 0;
  
  // Place alphabets and digits
  // alternatively
  while (i < n && j < m)
  {
    // If current character
    // needs to be alphabet
    if (flag != 0)
      ans += s1[i++];
  
    // If current character
    // needs to be a digit
    else
      ans += s2[j++];
  
    // Flip flag for alternate
    // arrangement
    if(flag == 1)
      flag = 0;
    else
      flag = 1;
  }
  
  // Return resultant String
  return ans;
}
 
// Driver Code
// Given String
let str = "geeks2020";
 
// Function Call
document.write(rearrange(str) + "<br>");
 
// This code is contributed by patel2127
</script>

g2e0e2k00

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