Count N-length strings consisting only of vowels sorted lexicographically

C++

C

Java

Python3

C#

Javascript

C++

C

Java

Python3

C#

Javascript

C++

C

Java

Python3

C#

Javascript

C++

C

Java

Python

C#

Javascript

0 0 15 minutes read

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++ 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

#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 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 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# 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.

<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

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++ 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;
}

#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 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 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# 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

<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>

Output

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:-

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.

#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.

#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 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 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# 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.

<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>

Output

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++ 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

#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 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

# 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# 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

Number of strings starting with

Total Possible strings

Total Possible strings

<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>

Output

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 zambiatek!