Disposición de los caracteres de una palabra de modo que todas las vocales estén en lugares impares

Dada una string ‘S’ que contiene vocales y consonantes de alfabetos ingleses en minúsculas. La tarea es encontrar el número de formas en que los caracteres de la palabra se pueden organizar de manera que las vocales ocupen solo las posiciones impares.

Ejemplos: 

Entrada: geeks 
Salida: 36 

Entrada: publicar 
Salida: 1440 
 

Acercarse: 
 

Primero encuentre el número total. de lugares impares y lugares pares en la palabra dada.
Número total de lugares pares = piso (longitud de palabra/2) 
Número total de lugares impares = longitud de palabra – total de lugares pares
Consideremos la string «contribuir», entonces hay 10 letras en la palabra dada y hay 5 lugares impares, 5 pares lugares, 4 vocales y 6 consonantes.
Marquemos estas posiciones como abajo: 
(1) (2) (3) (4) (5) (6) (7) (8) (9) (10)
Ahora, 4 vocales se pueden colocar en cualquiera de los cinco lugares, marcados 1, 3, 5, 7, 9. 
El número de formas de ordenar las vocales = 5_P_4 = 5! = 120
Además, las 6 consonantes se pueden organizar en las 6 posiciones restantes. 
Número de formas de estos arreglos = 6_P_6 = 6! = 720.
Número total de vías = (120 x 720) = 86400 
 

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

// C++ program to find the number of ways
// in which the characters of the word
// can be arranged such that the vowels
// occupy only the odd positions
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the
// factorial of a number
int fact(int n)
{
    int f = 1;
    for (int i = 2; i <= n; i++) {
        f = f * i;
    }
 
    return f;
}
 
// calculating nPr
int npr(int n, int r)
{
    return fact(n) / fact(n - r);
}
 
// Function to find the number of ways
// in which the characters of the word
// can be arranged such that the vowels
// occupy only the odd positions
int countPermutations(string str)
{
    // Get total even positions
    int even = floor(str.length() / 2);
 
    // Get total odd positions
    int odd = str.length() - even;
 
    int ways = 0;
 
    // Store frequency of each character of
    // the string
    int freq[26] = { 0 };
    for (int i = 0; i < str.length(); i++) {
        ++freq[str[i] - 'a'];
    }
 
    // Count total number of vowels
    int nvowels
        = freq[0] + freq[4]
          + freq[8] + freq[14]
          + freq[20];
 
    // Count total number of consonants
    int nconsonants
        = str.length() - nvowels;
 
    // Calculate the total number of ways
    ways = npr(odd, nvowels) * npr(nconsonants, nconsonants);
 
    return ways;
}
 
// Driver code
int main()
{
    string str = "geeks";
 
    cout << countPermutations(str);
 
    return 0;
}

// Java program to find the number of ways
// in which the characters of the word
// can be arranged such that the vowels
// occupy only the odd positions
class GFG{
// Function to return the
// factorial of a number
static int fact(int n)
{
    int f = 1;
    for (int i = 2; i <= n; i++) {
        f = f * i;
    }
 
    return f;
}
 
// calculating nPr
static int npr(int n, int r)
{
    return fact(n) / fact(n - r);
}
 
// Function to find the number of ways
// in which the characters of the word
// can be arranged such that the vowels
// occupy only the odd positions
static int countPermutations(String str)
{
    // Get total even positions
    int even = (int)Math.floor((double)(str.length() / 2));
 
    // Get total odd positions
    int odd = str.length() - even;
 
    int ways = 0;
 
    // Store frequency of each character of
    // the string
    int[] freq=new int[26];
    for (int i = 0; i < str.length(); i++) {
        freq[(int)(str.charAt(i)-'a')]++;
    }
 
    // Count total number of vowels
    int nvowels= freq[0] + freq[4]+ freq[8]
                + freq[14]+ freq[20];
 
    // Count total number of consonants
    int nconsonants= str.length() - nvowels;
 
    // Calculate the total number of ways
    ways = npr(odd, nvowels) * npr(nconsonants, nconsonants);
 
    return ways;
}
 
// Driver code
public static void main(String[] args)
{
    String str = "geeks";
 
    System.out.println(countPermutations(str));
}
}
// This code is contributed by mits

# Python3 program to find the number
# of ways in which the characters
# of the word can be arranged such
# that the vowels occupy only the
# odd positions
import math
 
# Function to return the factorial
# of a number
def fact(n):
    f = 1;
    for i in range(2, n + 1):
        f = f * i;
 
    return f;
 
# calculating nPr
def npr(n, r):
    return fact(n) / fact(n - r);
 
# Function to find the number of
# ways in which the characters of
# the word can be arranged such
# that the vowels occupy only the
# odd positions
def countPermutations(str):
 
    # Get total even positions
    even = math.floor(len(str) / 2);
 
    # Get total odd positions
    odd = len(str) - even;
 
    ways = 0;
 
    # Store frequency of each
    # character of the string
    freq = [0] * 26;
    for i in range(len(str)):
        freq[ord(str[i]) - ord('a')] += 1;
 
    # Count total number of vowels
    nvowels = (freq[0] + freq[4] + freq[8] +
               freq[14] + freq[20]);
 
    # Count total number of consonants
    nconsonants = len(str) - nvowels;
 
    # Calculate the total number of ways
    ways = (npr(odd, nvowels) *
            npr(nconsonants, nconsonants));
 
    return int(ways);
 
# Driver code
str = "geeks";
 
print(countPermutations(str));
     
# This code is contributed by mits

// C# program to find the number of ways
// in which the characters of the word
// can be arranged such that the vowels
// occupy only the odd positions
using System;
class GFG{
// Function to return the
// factorial of a number
static int fact(int n)
{
    int f = 1;
    for (int i = 2; i <= n; i++) {
        f = f * i;
    }
 
    return f;
}
 
// calculating nPr
static int npr(int n, int r)
{
    return fact(n) / fact(n - r);
}
 
// Function to find the number of ways
// in which the characters of the word
// can be arranged such that the vowels
// occupy only the odd positions
static int countPermutations(String str)
{
    // Get total even positions
    int even = (int)Math.Floor((double)(str.Length / 2));
 
    // Get total odd positions
    int odd = str.Length - even;
 
    int ways = 0;
 
    // Store frequency of each character of
    // the string
    int[] freq=new int[26];
    for (int i = 0; i < str.Length; i++) {
        freq[(int)(str[i]-'a')]++;
    }
 
    // Count total number of vowels
    int nvowels= freq[0] + freq[4]+ freq[8]
                + freq[14]+ freq[20];
 
    // Count total number of consonants
    int nconsonants= str.Length - nvowels;
 
    // Calculate the total number of ways
    ways = npr(odd, nvowels) * npr(nconsonants, nconsonants);
 
    return ways;
}
 
// Driver code
static void Main()
{
    String str = "geeks";
 
    Console.WriteLine(countPermutations(str));
}
}
// This code is contributed by mits

<?php
// PHP program to find the number
// of ways in which the characters
// of the word can be arranged such
// that the vowels occupy only the
// odd positions
 
// Function to return the
// factorial of a number
function fact($n)
{
    $f = 1;
    for ($i = 2; $i <= $n; $i++)
    {
        $f = $f * $i;
    }
 
    return $f;
}
 
// calculating nPr
function npr($n, $r)
{
    return fact($n) / fact($n - $r);
}
 
// Function to find the number
// of $ways in which the characters
// of the word can be arranged such
// that the vowels occupy only the
// odd positions
function countPermutations($str)
{
    // Get total even positions
    $even = floor(strlen($str)/ 2);
 
    // Get total odd positions
    $odd = strlen($str) - $even;
 
    $ways = 0;
 
    // Store $frequency of each
    // character of the string
    $freq = array_fill(0, 26, 0);
    for ($i = 0; $i < strlen($str); $i++)
    {
        ++$freq[ord($str[$i]) - ord('a')];
    }
 
    // Count total number of vowels
    $nvowels= $freq[0] + $freq[4] +
              $freq[8] + $freq[14] +
              $freq[20];
 
    // Count total number of consonants
    $nconsonants= strlen($str) - $nvowels;
 
    // Calculate the total number of ways
    $ways = npr($odd, $nvowels) *
            npr($nconsonants, $nconsonants);
 
    return $ways;
}
 
// Driver code
$str = "geeks";
 
echo countPermutations($str);
     
// This code is contributed by mits
?>

<script>
// Javascript program to find the number
// of ways in which the characters
// of the word can be arranged such
// that the vowels occupy only the
// odd positions
 
// Function to return the
// factorial of a number
function fact(n)
{
    let f = 1;
    for (let i = 2; i <= n; i++)
    {
        f = f * i;
    }
 
    return f;
}
 
// calculating nPr
function npr(n, r)
{
    return fact(n) / fact(n - r);
}
 
// Function to find the number
// of ways in which the characters
// of the word can be arranged such
// that the vowels occupy only the
// odd positions
function countPermutations(str)
{
    // Get total even positions
    let even = Math.floor(str.length/ 2);
 
    // Get total odd positions
    let odd = str.length - even;
 
    let ways = 0;
 
    // Store frequency of each
    // character of the string
    let freq = new Array(26).fill(0);
    for (let i = 0; i < str.length; i++)
    {
        ++freq[str.charCodeAt(i) - 'a'.charCodeAt(0)];
    }
 
    // Count total number of vowels
    let nvowels= freq[0] + freq[4] +
            freq[8] + freq[14] +
            freq[20];
 
    // Count total number of consonants
    let nconsonants= str.length - nvowels;
 
    // Calculate the total number of ways
    ways = npr(odd, nvowels) *
            npr(nconsonants, nconsonants);
 
    return ways;
}
 
// Driver code
let str = "geeks";
 
document.write(countPermutations(str));
     
// This code is contributed by gfgking
</script>

36

Complejidad de tiempo: O(n) donde n es la longitud de la string

Espacio Auxiliar: O(26)