Given an integer N, the task is to count all possible strings of length N consisting of vowels {a, e, i, o, u} that can be formed such that each string is sorted in lexicographical order.
Examples:
Input: N = 2
Output: 15
Explanation: The strings of length 2 which are sorted in lexicographical order are [“aa”, “ae”, “ai”, “ao”, “au”, “ee”, “ei”, “eo”, “eu”, “ii”, “io”, “iu”, “oo”, “ou”, “uu”].Input: N = 1
Output: 5
Explanation: The strings of length 1 which are sorted in lexicographical order are [“a”, “e”, “i”, “o”, “u”].
Naive Approach: The simplest approach is to generate all possible strings of length N such that each string is sorted in lexicographical order. Print the count obtained after completing the steps.
Recursive Approach: Keep track of the vowel added to the string so that the next vowel added to the string is always Lexicographically greater.
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 indexint 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 indexint 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 codeint 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 lexicographicallyimport 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 indexdef 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 = 2print(countVowelStrings(n))# This code is contributed by divyeshrabadiya07. |
C#
// C# program to illustrate Count of N-length strings// consisting only of vowels sorted lexicographicallyusing 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> |
Output
15
Time Complexity: O(N!)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use Dynamic Programming. Below are some observations to solve the given problem:
- Count of lexicographically sorted strings of length 1 starting from characters a, e, i, o, and u is 1.
- Count of strings of length 2 that are in lexicographical order starting from characters a, e, i, o, and u is given by:
- The count of lexicographically sorted strings of length 2 starting from characters a is given by the count of the lexicographical strings of length 1 starting from character greater than or equal to a. Therefore, the count is 5.
- The count of lexicographically sorted strings of length 2 starting from characters e is given by the count of the lexicographical strings of length 1 starting from character greater than or equal to e. Therefore, the count is 4.
- The count of lexicographically sorted strings of length 2 starting from characters i is given by the count of the lexicographical strings of length 1 starting from character greater than or equal to i. Therefore, the count is 3.
- The count of lexicographically sorted strings of length 2 starting from characters o is given by the count of the lexicographical strings of length 1 starting from character greater than or equal to o. Therefore, the count is 2.
- The count of lexicographically sorted strings of length 2 starting from characters u is given by the count of the lexicographical strings of length 1 starting from character greater than or equal to u. Therefore, the count is 1.
- Therefore, the total count of strings length 2 is given by: 5 + 4 + 3 + 2 + 1 = 15.
- By observing the above pattern the count of strings of length N starting from each vowel character ch is given by the sum of the count of the lexicographical strings of length (N – 1) starting from character greater than or equal to ch.
Follow the steps below to solve the problem:
- Create a 2D array, dp[N + 1][6] where dp[i][j] represents the number of lexicographically sorted strings of length i that can be constructed using the first j vowels and initialize dp[1][1] with 1.
- Iterate over the first row using variable j, set dp[1][j] = dp[1][j – 1] + 1 as the string of length 1 are always sorted in lexicographically order.
- Traverse the 2D array dp[][] and update each dp state as dp[i][j] = dp[i][j – 1] + dp[i – 1][j], where dp[i][j – 1] will give the count of lexicographical string length N and dp[i – 1][j] will give the count of lexicographical string length (N – 1).
- After the above steps, print the value of dp[N][5] as the total count of resultant strings.
Below is the implementation of the above approach:
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// lexicographicallyint 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 Codeint 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// lexicographicallyint 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 Codeint main() { int N = 2; printf("%d",findNumberOfStrings(N)); return 0;}// This code was contributed by Alok Khansali |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{ // Function to count N-length strings// consisting of vowels only sorted// lexicographicallystatic 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 Codepublic 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 lexicographicallydef 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 Codeif __name__ == '__main__': N = 2 # Function Call print(findNumberOfStrings(N))# This code is contributed by Mohit Kumar 29 |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to count N-length strings// consisting of vowels only sorted// lexicographicallystatic 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 Codepublic 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// lexicographicallyfunction 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> |
Output
15
Time Complexity: O(N*5)
Auxiliary Space: O(N*5)
Efficient Approach: The above approach can further be simplified to linear time and constant space.
Here are some of the observations for different lengths of strings:-
| N | Number of strings starting with | Total Possible strings | ||||
| ‘a’ | ‘e’ | ‘i’ | ‘o’ | ‘u’ | ||
| 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 |
It is seen that for each value of N, number of strings possible is dependent on the previous value of N (N-1).
Value of any column in the Nth row is the sum of all columns in the (N-1)th row, starting from right hand side upto that column number.
C++
#include <bits/stdc++.h>using namespace std;// Function to count N-length strings// consisting of vowels only sorted// lexicographicallyint 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 Codeint 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// lexicographicallyint 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 Codeint main(){ int N = 2; printf("%d",findNumberOfStrings(N)); return 0;}//This code was contributed by Alok Khansali |
Java
// Java program for the above approachimport 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# lexicographicallydef 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 ansN = 2 # Function Callprint(findNumberOfStrings(N))# This code is contributed by decode2207. |
C#
// C# program to implement above approachusing 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// lexicographicallyfunction 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 resultreturn ans}let N = 2// Function Calldocument.write(findNumberOfStrings(N));// This code is contributed by Lovely Jain</script> |
Output
15
Time Complexity: O(5*N)
Space Complexity: O(1)
Efficient Approach: The same idea of the above dp approach can be implemented in constant time and constant space.
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// lexicographicallyint findNumberOfStrings(int n){ return (n+1)*(n+2)*(n+3)*(n+4)/24;}// Driver Codeint 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 Codeint 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 approachimport java.util.*;class GFG{ // Function to count N-length strings// consisting of vowels only sorted// lexicographicallystatic int findNumberOfStrings(int n){ return (n+1)*(n+2)*(n+3)*(n+4)/24;}// Driver Codepublic 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 lexicographicallydef findNumberOfStrings(n): return int((n+1)*(n+2)*(n+3)*(n+4)/24)# Driver Codeif __name__ == '__main__': N = 2 # Function Call print(findNumberOfStrings(N))# This code is contributed by Kartik Singh |
C#
// C# program to implement// the above approachusing System;class GFG{ // Function to count N-length strings// consisting of vowels only sorted// lexicographicallystatic int findNumberOfStrings(int n){ return (n+1)*(n+2)*(n+3)*(n+4)/24;}// Driver Codepublic 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// lexicographicallyfunction findNumberOfStrings(n){ return (n+1)*(n+2)*(n+3)*(n+4)/24;}// Driver Code let N = 2; // Function Call document.write(findNumberOfStrings(N)); </script> |
Output
15
Time Complexity: O(1)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
