Print all Substrings of a String that has equal number of vowels and consonants

Given a string S, the task is to print all the substrings of a string that has an equal number of vowels and consonants.

Examples:

Input: “geeks”
Output: “ge”, “geek”, “eeks”, “ek”

Input: “coding”
Output: “co”, “codi”, “od”, “odin”, “di”, “in”

Naive Approach: The basic approach to solve this problem is to generate all the substrings and then for each substring count the number of vowels and consonants present in it. If they are equal print it. 

Time complexity: O(N^3)
Auxiliary Space: O(1)

Efficient Approach: To solve the problem follow the below idea:

In this approach, we traverse through two loops and store the start and end indices of every substring in a vector that has an equal number of vowels and consonants. 

Steps involved in this approach:

• First, we traverse a for loop which depicts the starting positions of the substrings. 
• Then an inner loop is traversed which in every iteration checks if the current character is a vowel or consonant.
• We increment the count of vowels or consonants based on these if conditions.
• If at any instance the number of vowels and consonants are equal then we add the start and end indices of that current substring.
• After both loops are traversed then print all the substrings with the indices present in the vector.

Below is the code for the above approach:

// C++ code for above approach
#include <bits/stdc++.h>
using namespace std;

// Initialising vector
vector<pair<int, int> > ans;

// Function to check if character is
// vowel or consonent.
bool isVowel(char c)
{
    return c == 'a' || c == 'e' || c == 'i' || c == 'o'
           || c == 'u';
}

// Function to print all
// possible substring
void all_substring(string s, int n)
{
    for (int i = 0; i < n; i++) {
        int count_vowel = 0, count_consonant = 0;
        for (int j = i; j < n; j++) {

            // If vowel increase its count
            if (isVowel(s[j]))
                count_vowel++;

            // If consonent increase
            // its count
            else
                count_consonant++;

            // If equal vowel and consonant
            // in the substring store the
            // index of the starting and
            // ending point of that substring
            if (count_vowel == count_consonant)
                ans.push_back({ i, j });
        }
    }

    // Printing all substrings
    for (auto x : ans) {
        int l = x.first;
        int r = x.second;

        cout << s.substr(l, r - l + 1) << endl;
    }
}

// Driver Code
int main()
{
    string s = "geeks";
    int n = s.size();

    // Function call
    all_substring(s, n);
    return 0;
}

Time Complexity: O(N²)
Auxiliary Space: O(N)

Given a string S, the task is to print all the substrings of a string that has an equal number of vowels and consonants.

Examples:

Input: “geeks”
Output: “ge”, “geek”, “eeks”, “ek”

Input: “coding”
Output: “co”, “codi”, “od”, “odin”, “di”, “in”

Naive Approach: The basic approach to solve this problem is to generate all the substrings and then for each substring count the number of vowels and consonants present in it. If they are equal print it. 

Time complexity: O(N^3)
Auxiliary Space: O(1)

Efficient Approach: To solve the problem follow the below idea:

In this approach, we traverse through two loops and store the start and end indices of every substring in a vector that has an equal number of vowels and consonants. 

Steps involved in this approach:

• First, we traverse a for loop which depicts the starting positions of the substrings. 
• Then an inner loop is traversed which in every iteration checks if the current character is a vowel or consonant.
• We increment the count of vowels or consonants based on these if conditions.
• If at any instance the number of vowels and consonants are equal then we add the start and end indices of that current substring.
• After both loops are traversed then print all the substrings with the indices present in the vector.

Below is the code for the above approach:

// C++ code for above approach
#include <bits/stdc++.h>
using namespace std;

// Initialising vector
vector<pair<int, int> > ans;

// Function to check if character is
// vowel or consonent.
bool isVowel(char c)
{
    return c == 'a' || c == 'e' || c == 'i' || c == 'o'
           || c == 'u';
}

// Function to print all
// possible substring
void all_substring(string s, int n)
{
    for (int i = 0; i < n; i++) {
        int count_vowel = 0, count_consonant = 0;
        for (int j = i; j < n; j++) {

            // If vowel increase its count
            if (isVowel(s[j]))
                count_vowel++;

            // If consonent increase
            // its count
            else
                count_consonant++;

            // If equal vowel and consonant
            // in the substring store the
            // index of the starting and
            // ending point of that substring
            if (count_vowel == count_consonant)
                ans.push_back({ i, j });
        }
    }

    // Printing all substrings
    for (auto x : ans) {
        int l = x.first;
        int r = x.second;

        cout << s.substr(l, r - l + 1) << endl;
    }
}

// Driver Code
int main()
{
    string s = "geeks";
    int n = s.size();

    // Function call
    all_substring(s, n);
    return 0;
}

Time Complexity: O(N²)
Auxiliary Space: O(N)