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)