Cuente strings de longitud N que consisten solo en vocales ordenadas lexicográficamente

Dado un número entero N , la tarea es contar todas las strings posibles de longitud N que consisten en vocales {a, e, i, o, u} que se pueden formar de tal manera que cada string se clasifique en orden lexicográfico .

Ejemplos:

Entrada: N = 2
Salida: 15
Explicación: Las strings de longitud 2 que están ordenadas en orden lexicográfico son [“aa”, “ae”, “ai”, “ao”, “au”, “ee”, “ei” , “eo”, “eu”, “ii”, “io”, “iu”, “oo”, “ou”, “uu”].

Entrada: N = 1
Salida: 5
Explicación: Las strings de longitud 1 que están ordenadas en orden lexicográfico son [“a”, “e”, “i”, “o”, “u”].

Enfoque ingenuo: el enfoque más simple es generar todas las strings posibles de longitud N de modo que cada string se clasifique en orden lexicográfico. Imprime el conteo obtenido luego de completar los pasos. 

Enfoque recursivo: realice un seguimiento de la vocal añadida a la string para que la siguiente vocal añadida a la string sea siempre lexicográficamente mayor.

C++

// C++ program to illustrate Count of N-length strings
// consisting only of vowels sorted lexicographically
 
#include <iostream>
using namespace std;
// to keep the string in lexicographically sorted order use
// start index
// to add the vowels starting the from that index
int countstrings(int n, int start)
{
    // base case: if string length is 0 add to the count
    if (n == 0) {
        return 1;
    }
    int cnt = 0;
    // if last character in string is 'e'
    // add vowels starting from  'e'
    // i.e    'e','i','o','u'
    for (int i = start; i < 5; i++) {
        // decrease the length of string
        cnt += countstrings(n - 1, i);
    }
    return cnt;
}
int countVowelStrings(int n)
{
    //  char arr[5]={'a','e','i','o','u'};
    // starting from index 0 add the vowels to strings
    return countstrings(n, 0);
}
int main()
{
    int n = 2;
    cout << countVowelStrings(n);
    return 0;
}
// This code is contributed by Deepak Chowdary

C

#include <stdio.h>
// to keep the string in lexicographically sorted order use
// start index
// to add the vowels starting the from that index
int countstrings(int n, int start)
{
    // base case: if string length is 0 add to the count
    if (n == 0) {
        return 1;
    }
    int cnt = 0;
    // if last character in string is 'e'
    // add vowels starting from  'e'
    // i.e    'e','i','o','u'
    for (int i = start; i < 5; i++) {
        // decrease the length of string
        cnt += countstrings(n - 1, i);
    }
    return cnt;
}
int countVowelStrings(int n)
{
    //  char arr[5]={'a','e','i','o','u'};
    // starting from index 0 add the vowels to strings
    return countstrings(n, 0);
}
//driver code
int main() {
 
    int n = 2;
    printf("%d",countVowelStrings(n));
    return 0;
}
 
// This code is contributed by thecodealpha.

Java

// Java program to illustrate Count of N-length strings
// consisting only of vowels sorted lexicographically
import java.util.*;
public class Main
{
   
    // to keep the string in lexicographically sorted order use
    // start index
    // to add the vowels starting the from that index
    static int countstrings(int n, int start)
    {
        
        // base case: if string length is 0 add to the count
        if (n == 0) {
            return 1;
        }
        int cnt = 0;
        
        // if last character in string is 'e'
        // add vowels starting from  'e'
        // i.e    'e','i','o','u'
        for (int i = start; i < 5; i++)
        {
            
            // decrease the length of string
            cnt += countstrings(n - 1, i);
        }
        return cnt;
    }
    static int countVowelStrings(int n)
    {
        
        //  char arr[5]={'a','e','i','o','u'};
        // starting from index 0 add the vowels to strings
        return countstrings(n, 0);
    }
     
    public static void main(String[] args) {
        int n = 2;
        System.out.print(countVowelStrings(n));
    }
}
 
// This code is contributed by divyesh072019.

Python3

# Python3 program to illustrate Count of N-length strings
# consisting only of vowels sorted lexicographically
 
# to keep the string in lexicographically sorted order use
# start index
# to add the vowels starting the from that index
def countstrings(n, start):
   
    # base case: if string length is 0 add to the count
    if n == 0:
        return 1
    cnt = 0
     
    # if last character in string is 'e'
    # add vowels starting from  'e'
    # i.e    'e','i','o','u'
    for i in range(start, 5):
       
        # decrease the length of string
        cnt += countstrings(n - 1, i)
    return cnt
     
def countVowelStrings(n):
   
    #  char arr[5]={'a','e','i','o','u'};
    # starting from index 0 add the vowels to strings
    return countstrings(n, 0)
 
n = 2
print(countVowelStrings(n))
 
# This code is contributed by divyeshrabadiya07.

C#

// C# program to illustrate Count of N-length strings
// consisting only of vowels sorted lexicographically
using System;
using System.Collections.Generic;
class GFG {
    
    // to keep the string in lexicographically sorted order use
    // start index
    // to add the vowels starting the from that index
    static int countstrings(int n, int start)
    {
       
        // base case: if string length is 0 add to the count
        if (n == 0) {
            return 1;
        }
        int cnt = 0;
       
        // if last character in string is 'e'
        // add vowels starting from  'e'
        // i.e    'e','i','o','u'
        for (int i = start; i < 5; i++)
        {
           
            // decrease the length of string
            cnt += countstrings(n - 1, i);
        }
        return cnt;
    }
    static int countVowelStrings(int n)
    {
       
        //  char arr[5]={'a','e','i','o','u'};
        // starting from index 0 add the vowels to strings
        return countstrings(n, 0);
    }
 
  static void Main() {
    int n = 2;
    Console.Write(countVowelStrings(n));
  }
}
 
// This code is contributed by decode2207.

Javascript

<script>
    // Javascript program to illustrate Count of N-length strings
    // consisting only of vowels sorted lexicographically
     
    // to keep the string in lexicographically sorted order use
    // start index
    // to add the vowels starting the from that index
    function countstrings(n, start)
    {
        
        // base case: if string length is 0 add to the count
        if (n == 0) {
            return 1;
        }
        let cnt = 0;
        
        // if last character in string is 'e'
        // add vowels starting from  'e'
        // i.e    'e','i','o','u'
        for (let i = start; i < 5; i++)
        {
            
            // decrease the length of string
            cnt += countstrings(n - 1, i);
        }
        return cnt;
    }
    function countVowelStrings(n)
    {
        
        //  char arr[5]={'a','e','i','o','u'};
        // starting from index 0 add the vowels to strings
        return countstrings(n, 0);
    }
     
    let n = 2;
    document.write(countVowelStrings(n));
  
 // This code is contributed by suresh07.
</script>
Producción

15

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

Enfoque Eficiente: Para optimizar el enfoque anterior, la idea es utilizar Programación Dinámica . A continuación se presentan algunas observaciones para resolver el problema planteado:

  • El recuento de strings ordenadas lexicográficamente de longitud 1 a partir de los caracteres a, e, i, o y u es 1 .
  • El recuento de strings de longitud 2 que están en orden lexicográfico a partir de los caracteres a, e, i, o y u viene dado por:
    • El recuento de strings ordenadas lexicográficamente de longitud 2 a partir del carácter a viene dado por el recuento de strings lexicográficas de longitud 1 a partir del carácter mayor o igual que  a . Por lo tanto, la cuenta es 5 .
    • El recuento de strings ordenadas lexicográficamente de longitud 2 a partir de los caracteres e viene dado por el recuento de strings lexicográficas de longitud 1 a partir del carácter mayor o igual que  e . Por lo tanto, la cuenta es 4 .
    • El recuento de strings ordenadas lexicográficamente de longitud 2 a partir de los caracteres i viene dado por el recuento de strings lexicográficas de longitud 1 a partir del carácter mayor o igual que  i . Por lo tanto, la cuenta es 3 .
    • El recuento de strings ordenadas lexicográficamente de longitud 2 a partir de los caracteres o viene dado por el recuento de strings lexicográficas de longitud 1 a partir del carácter mayor o igual que  o . Por lo tanto, la cuenta es 2 .
    • El recuento de strings ordenadas lexicográficamente de longitud 2 a partir de los caracteres u viene dado por el recuento de strings lexicográficas de longitud 1 a partir del carácter mayor o igual que u . Por lo tanto, la cuenta es 1 .
  • Por lo tanto, el recuento total de strings de longitud 2  está dado por: 5 + 4 + 3 + 2 + 1 = 15 .
  • Al observar el patrón anterior, el recuento de strings de longitud N a partir de cada carácter vocálico ch viene dado por la suma del recuento de strings lexicográficas de longitud (N – 1) a partir del carácter mayor o igual que  ch .

Siga los pasos a continuación para resolver el problema:

  • Cree una array 2D, dp[N + 1][6] donde dp[i][j] representa el número de strings ordenadas lexicográficamente de longitud i que se pueden construir usando las primeras j vocales e inicialice dp[1][1] con 1 .
  • Iterar sobre la primera fila usando la variable j, establecer dp[1][j] = dp[1][j – 1] + 1 ya que la string de longitud 1 siempre se ordena en orden lexicográfico.
  • Atraviese la array 2D dp[][] y actualice cada estado de dp como dp[i][j] = dp[i][j – 1] + dp[i – 1][j] , donde dp[i][j – 1] dará el recuento de la longitud de la string lexicográfica N y dp[i – 1][j] dará el recuento de la longitud de la string lexicográfica (N – 1) .
  • Después de los pasos anteriores, imprima el valor de dp[N][5] como el recuento total de strings resultantes.

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 count N-length strings
// consisting of vowels only sorted
// lexicographically
int findNumberOfStrings(int n)
{
    // Stores count of strings consisting
    // of vowels sorted lexicographically
    // of all possible lengths
    vector<vector<int> > DP(n + 1,
                            vector<int>(6));
 
    // Initialize DP[1][1]
    DP[1][1] = 1;
 
    // Traverse the matrix row-wise
    for (int i = 1; i < n + 1; i++) {
 
        for (int j = 1; j < 6; j++) {
 
            // Base Case
            if (i == 1) {
                DP[i][j] = DP[i][j - 1] + 1;
            }
 
            else {
                DP[i][j] = DP[i][j - 1]
                           + DP[i - 1][j];
            }
        }
    }
 
    // Return the result
    return DP[n][5];
}
 
// Driver Code
int main()
{
    int N = 2;
 
    // Function Call
    cout << findNumberOfStrings(N);
 
    return 0;
}

C

#include <stdio.h>
// Function to count N-length strings
// consisting of vowels only sorted
// lexicographically
int findNumberOfStrings(int n)
{
    // Stores count of strings consisting
    // of vowels sorted lexicographically
    // of all possible lengths
    int DP[n + 1][6];
    // Initialize DP[1][1]
    DP[1][1] = 1;
    // Traverse the matrix row-wise
    for (int i = 1; i < n + 1; i++) {
 
        for (int j = 1; j < 6; j++) {
 
            // Base Case
            if (i == 1)
                DP[i][j] = DP[i][j - 1] + 1;
            else
                DP[i][j] = DP[i][j - 1] + DP[i - 1][j];
        }
    }
    // Return the result
    return DP[n][5];
}
// Driver Code
int main() {
 
    int N = 2;
    printf("%d",findNumberOfStrings(N));
    return 0;
}
 
// This code was contributed by Alok Khansali

Java

// Java program to implement
// the above approach
import java.util.*;
class GFG{
   
// Function to count N-length strings
// consisting of vowels only sorted
// lexicographically
static int findNumberOfStrings(int n)
{
  // Stores count of strings consisting
  // of vowels sorted lexicographically
  // of all possible lengths
  int DP[][] = new int [n + 1][6];
 
  // Initialize DP[1][1]
  DP[1][1] = 1;
 
  // Traverse the matrix row-wise
  for (int i = 1; i < n + 1; i++)
  {
    for (int j = 1; j < 6; j++)
    {
      // Base Case
      if (i == 1)
      {
        DP[i][j] = DP[i][j - 1] + 1;
      }
 
      else
      {
        DP[i][j] = DP[i][j - 1] +
                   DP[i - 1][j];
      }
    }
  }
 
  // Return the result
  return DP[n][5];
}
 
// Driver Code
public static void main(String[] args)
{
  int N = 2;
 
  // Function Call
  System.out.print(findNumberOfStrings(N));
}
}
 
// This code is contributed by sanjoy_62

Python3

# Python3 program for the
# above approach
 
# Function to count N-length
# strings consisting of vowels
# only sorted lexicographically
def findNumberOfStrings(n):
   
    # Stores count of strings
    # consisting of vowels
    # sorted lexicographically
    # of all possible lengths
    DP = [[0 for i in range(6)]
             for i in range(n + 1)]
 
    # Initialize DP[1][1]
    DP[1][1] = 1
 
    # Traverse the matrix row-wise
    for i in range(1, n + 1):
        for j in range(1, 6):
 
            #Base Case
            if (i == 1):
                DP[i][j] = DP[i][j - 1] + 1
            else:
                DP[i][j] = DP[i][j - 1]+ DP[i - 1][j]
 
    # Return the result
    return DP[n][5]
 
# Driver Code
if __name__ == '__main__':
   
    N = 2
 
    # Function Call
    print(findNumberOfStrings(N))
 
# This code is contributed by Mohit Kumar 29

C#

// C# program to implement
// the above approach
using System;
class GFG{
   
// Function to count N-length strings
// consisting of vowels only sorted
// lexicographically
static int findNumberOfStrings(int n)
{
  // Stores count of strings consisting
  // of vowels sorted lexicographically
  // of all possible lengths
  int[,] DP = new int [n + 1, 6];
 
  // Initialize DP[1][1]
  DP[1, 1] = 1;
 
  // Traverse the matrix row-wise
  for (int i = 1; i < n + 1; i++)
  {
    for (int j = 1; j < 6; j++)
    {
      // Base Case
      if (i == 1)
      {
        DP[i, j] = DP[i, j - 1] + 1;
      }
 
      else
      {
        DP[i, j] = DP[i, j - 1] +
                   DP[i - 1, j];
      }
    }
  }
 
  // Return the result
  return DP[n, 5];
}
 
// Driver Code
public static void Main(string[] args)
{
  int N = 2;
 
  // Function Call
  Console.Write(findNumberOfStrings(N));
}
}
 
// This code is contributed by Chitranayal

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to count N-length strings
// consisting of vowels only sorted
// lexicographically
function findNumberOfStrings(n)
{
  // Stores count of strings consisting
  // of vowels sorted lexicographically
  // of all possible lengths
  let DP = new Array(n + 1);
   
  // Loop to create 2D array using 1D array
    for (var i = 0; i < DP.length; i++) {
    DP[i] = new Array(2);
    }
     
    for (var i = 0; i < DP.length; i++) {
        for (var j = 0; j < DP.length; j++) {
        DP[i][j] = 0;
    }
    }
  
  // Initialize DP[1][1]
  DP[1][1] = 1;
  
  // Traverse the matrix row-wise
  for (let i = 1; i < n + 1; i++)
  {
    for (let j = 1; j < 6; j++)
    {
      // Base Case
      if (i == 1)
      {
        DP[i][j] = DP[i][j - 1] + 1;
      }
  
      else
      {
        DP[i][j] = DP[i][j - 1] +
                   DP[i - 1][j];
      }
    }
  }
  
  // Return the result
  return DP[n][5];
}
 
 
// Driver Code
 
  let N = 2;
  
  // Function Call
  document.write(findNumberOfStrings(N));
     
</script>
Producción

15

Complejidad de Tiempo: O(N*5)
Espacio Auxiliar: O(N*5)

Enfoque eficiente : el enfoque anterior se puede simplificar aún más a tiempo lineal y espacio constante.

Estas son algunas de las observaciones para diferentes longitudes de cuerdas:

norte Número de strings que comienzan con Strings posibles totales
‘a’ ‘mi’ ‘i’ ‘o’ ‘tú’
1 1 1 1 1 1 5
2 5 4 3 2 1 15
3 15 10 6 3 1 35
4 35 20 10 4 1 70

Se ve que para cada valor de N , el número de strings posibles depende del valor anterior de N (N-1) .

El valor de cualquier columna en la fila N es la suma de todas las columnas en la fila (N-1) , comenzando desde el lado derecho hasta ese número de columna.

C++

#include <bits/stdc++.h>
using namespace std;
 
// Function to count N-length strings
// consisting of vowels only sorted
// lexicographically
int findNumberOfStrings(int N)
{
    // Initializing vector to store count of strings.
    vector<int> counts(5, 1);
 
    for (int i = 2; i <= N; i++) {
        for (int j = 3; j >= 0; j--)
            counts[j] += counts[j + 1];
    }
 
    int ans = 0;
 
    // Summing up the total number of combinations.
    for (auto c : counts)
        ans += c;
 
    // Return the result
    return ans;
}
 
// Driver Code
int main()
{
    int N = 2;
 
    // Function Call
    cout << findNumberOfStrings(N);
 
    return 0;
}
 
// This code is contributed by Sarvesh Roshan.

C

#include <stdio.h>
// Function to count N-length strings
// consisting of vowels only sorted
// lexicographically
int findNumberOfStrings(int N)
{
    // Initializing vector to store count of strings.
    int counts[5];
    for(int i = 0; i < 5;i++)
      counts[i] = 1;
    for (int i = 2; i <= N; i++) {
        for (int j = 3; j >= 0; j--)
            counts[j] += counts[j + 1];
    }
    int ans = 0;
    // Summing up the total number of combinations.
    for (int c = 0; c < 5; c++)
        ans += counts;
    // Return the result
    return ans;
}
// Driver Code
int main()
{
    int N = 2;
    printf("%d",findNumberOfStrings(N));
    return 0;
}
//This code was contributed by Alok Khansali

Java

// Java program for the above approach
import java.util.*;
public class Main
{
    // Function to count N-length strings
    // consisting of vowels only sorted
    // lexicographically
    static int findNumberOfStrings(int N)
    {
        // Initializing vector to store count of strings.
        Vector<Integer> counts = new Vector<Integer>();
        for(int i = 0; i < 5; i++)
        {
            counts.add(1);
        }
      
        for (int i = 2; i <= N; i++) {
            for (int j = 3; j >= 0; j--)
                counts.set(j, counts.get(j) + counts.get(j + 1));
        }
      
        int ans = 0;
      
        // Summing up the total number of combinations.
        for(Integer c : counts)
            ans += c;
      
        // Return the result
        return ans;
    }
     
    public static void main(String[] args) {
        int N = 2;
  
        // Function Call
        System.out.print(findNumberOfStrings(N));
    }
}
 
// This code is contributed by mukesh07.

Python3

# Python3 program for the above approach
 
# Function to count N-length strings
# consisting of vowels only sorted
# lexicographically
def findNumberOfStrings(N):
    # Initializing vector to store count of strings.
    counts = []
    for i in range(5):
        counts.append(1)
   
    for i in range(2, N + 1):
        for j in range(3, -1, -1):
            counts[j] += counts[j + 1]
   
    ans = 0
   
    # Summing up the total number of combinations.
    for c in counts:
        ans += c
   
    # Return the result
    return ans
 
N = 2
   
# Function Call
print(findNumberOfStrings(N))
 
# This code is contributed by decode2207.

C#

// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
  // Function to count N-length strings
  // consisting of vowels only sorted
  // lexicographically
  static int findNumberOfStrings(int N)
  {
    // Initializing vector to store count of strings.
    List<int> counts = new List<int>();
    for(int i = 0 ; i < 5 ; i++)
    {
      counts.Add(1);
    }
 
    for (int i = 2 ; i <= N ; i++) {
      for (int j = 3 ; j >= 0 ; j--){
        counts[j] = counts[j] + counts[j+1];
      }
    }
 
    int ans = 0;
 
    // Summing up the total number of combinations.
    foreach (int c in counts)
      ans += c;
 
    // Return the result
    return ans;
  }
 
  // Driver code
  public static void Main(string[] args){
 
    int N = 2;
 
    // Function Call
    Console.Write(findNumberOfStrings(N));
 
  }
}
 
// This code is contributed by subhamgoyal2014.

Javascript

<script>
// Javascript program for above approach
 
// Function to count N-length strings
// consisting of vowels only sorted
// lexicographically
function findNumberOfStrings(N)
{
 
// Initializing vector to store count of strings.
let counts = [1, 1, 1, 1, 1];
 
for(let i = 2; i < N + 1; i++)
for(let j = 3; j >= 0; j--)
counts[j] += counts[j + 1]
 
let ans = 0;
 
// Summing up the total number of combinations.
for(let c in counts)
ans = ans + counts;
 
// Return the result
return ans
}
 
let N = 2
 
// Function Call
document.write(findNumberOfStrings(N));
 
// This code is contributed by Lovely Jain
</script>
Producción

15

Complejidad de tiempo: O(5*N)
Complejidad de espacio: O(1)

Enfoque eficiente: la misma idea del enfoque dp anterior se puede implementar en tiempo constante y espacio constante .

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count N-length strings
// consisting of vowels only sorted
// lexicographically
int findNumberOfStrings(int n)
{
    return (n+1)*(n+2)*(n+3)*(n+4)/24;
}
 
// Driver Code
int main()
{
    int N = 2;
 
    // Function Call
    cout << findNumberOfStrings(N);
 
    return 0;
}
// This code is contributed by Kartik Singh

C

#include <stdio.h>
int findNumberOfStrings(int n)
{
    return (n+1)*(n+2)*(n+3)*(n+4)/24;
}
// Driver Code
int main()
{
    int N = 2;
    printf("%d", findNumberOfStrings(N));
    return 0;
}
//This code has been added by Alok Khansali

Java

// Java program to implement
// the above approach
import java.util.*;
class GFG{
   
// Function to count N-length strings
// consisting of vowels only sorted
// lexicographically
static int findNumberOfStrings(int n)
{
 return (n+1)*(n+2)*(n+3)*(n+4)/24;
}
 
// Driver Code
public static void main(String[] args)
{
  int N = 2;
 
  // Function Call
  System.out.print(findNumberOfStrings(N));
}
}
 
// This code is contributed by Kartik Singh

Python

# Python3 program for the
# above approach
 
# Function to count N-length
# strings consisting of vowels
# only sorted lexicographically
def findNumberOfStrings(n):
    return int((n+1)*(n+2)*(n+3)*(n+4)/24)
 
# Driver Code
if __name__ == '__main__':
   
    N = 2
 
    # Function Call
    print(findNumberOfStrings(N))
 
# This code is contributed by Kartik Singh

C#

// C# program to implement
// the above approach
using System;
class GFG{
   
// Function to count N-length strings
// consisting of vowels only sorted
// lexicographically
static int findNumberOfStrings(int n)
{
  return (n+1)*(n+2)*(n+3)*(n+4)/24;
}
 
// Driver Code
public static void Main(string[] args)
{
  int N = 2;
 
  // Function Call
  Console.Write(findNumberOfStrings(N));
}
}
 
// This code is contributed by Kartik Singh

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to count N-length strings
// consisting of vowels only sorted
// lexicographically
function findNumberOfStrings(n)
{
    return (n+1)*(n+2)*(n+3)*(n+4)/24;
}
 
 
// Driver Code
 
  let N = 2;
  
  // Function Call
  document.write(findNumberOfStrings(N));
     
</script>
Producción

15

Complejidad de tiempo : O(1)

Espacio Auxiliar : O(1)

Publicación traducida automáticamente

Artículo escrito por iamrj846 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *