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>
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>
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>
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>
15
Complejidad de tiempo : O(1)
Espacio Auxiliar : O(1)