Given string str of size N consisting of uppercase and lowercase English letters. The task is to find all unique substrings containing only vowels.
Examples:
Input: str = “neveropen”
Output: “ee” , “e”, “o”
Explanation: There are multiple occurrences of some of the substrings like “ee” but these are the only unique substrings.Input: str = “TRAnsmission”
Output: “A”, “io”, “i”, “o”Input: str = “AioutraevbcUoee”
Output: “Aiou”, “Aio”, “Ai”, “A”, “iou”, “io”, “i”, “ou”, “o”, “u”, “ae”,
“a”, “e”, “Uoee”, “Uoe”, “Uo”, ” U”, “oee”, “oe”, “ee”
Naive Approach: The simplest approach is to generate all substrings and check each of them if they contain only vowels or not and if they are unique. Use the following steps:
- Generate all substrings of the string.
- Use map to keep track of unique substrings.
- If the substring consists of only vowels and is not on the map, add it to the map and store it as an answer.
- Print all the answers
Below is the implementation of the above approach:
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;// Function to check if a character is vowelbool isvowel(char ch){ return (ch == 'a' or ch == 'A' or ch == 'e' or ch == 'E' or ch == 'i' or ch == 'I' or ch == 'o' or ch == 'O' or ch == 'u' or ch == 'U');}// Function to check whether// string contains only vowelbool isvalid(string& s){ int n = s.length(); for (int i = 0; i < n; i++) { // Check if the character is // not vowel then invalid if (!isvowel(s[i])) return false; } return true;}// Function for generating // all unique substrings of only vowels.void generateVowelSubstrings(string params){ int ans = 0; unordered_map<string, bool> map; // Generate all substring of string for (int i = 0; i < params.length(); i++) { string temp = ""; for (int j = i; j < params.length(); j++) { temp += params[j]; // If temp contains only vowels if (isvalid(temp)) { map[temp] = true; } } } unordered_map<string, bool>::iterator itr; for (itr = map.begin(); itr != map.end(); ++itr) { // Printing all unique substrings. cout << itr->first << '\n'; }}// Driver codeint main(){ string str = "GeeksForGeeks"; generateVowelSubstrings(str); return 0;} |
Java
/*package whatever //do not write package name here */// Java code to implement the above approachimport java.io.*;import java.util.*;class GFG { // Function to check if a character is vowel public static boolean isVowel(char ch) { return (ch == 'a' || ch == 'A' || ch == 'e' || ch == 'E' || ch == 'i' || ch == 'I' || ch == 'o' || ch == 'O' || ch == 'u' || ch == 'U'); } // Function to check whether // string contains only vowel public static boolean isValid(String s) { int n = s.length(); for (int i = 0; i < n; i++) { // Check if the character is // not vowel then invalid if (!isVowel(s.charAt(i))) return false; } return true; } // Function for generating unique substrings of vowels. public static void generateVowelSubstrings(String string) { int ans = 0; HashMap<String, Boolean> map = new HashMap<>(); // Generate all subString of s for (int i = 0; i < string.length(); i++) { String temp = ""; for (int j = i; j < string.length(); j++) { temp += string.charAt(j); // If temp contains only vowels if (isValid(temp)) { // store it only if substring is absent // in map. map.putIfAbsent(temp, true); } } } for (String key : map.keySet()) { // printing all unique substring. System.out.println(key); } } // Driver Code public static void main(String[] args) { String str = "GeeksForGeeks"; generateVowelSubstrings(str); }}// This code is contributed by kaalel. |
Python3
# JavaScript code to implement above approach# Function to check if a character is voweldef isVowel(c): # Checking for vowels. return ((c == "a") or (c == "A") or (c == "e") or (c == "E") or (c == "i") or (c == "I") or (c == "o") or (c == "O") or (c == "u") or (c == "U"))# Extracting all the maximum length# sub-strings that contain only vowels.def vowelSubstrings(params): str = "" # Using map to remove identicals # substrings. e.g. AiotrfAio has 2 "Aio". map = {} for i in range(len(params)): subString = params[i: i + 1] if(isVowel(subString)): str += subString else: # Storing a substring only if # it is not empty. if len(str) != 0: map[str] = True str = "" if (len(str) != 0): map[str] = True return map # Function to generate all unique substrings # containing only vowelsdef generateVowelSubstrings(params): substringMap = vowelSubstrings(params) map = {} # map iterator. for itr in substringMap: x = itr # For each substring stored in map # generate all possible substrings. for i in range(len(x)): for l in range(1,len(x) - i+1): # Storing the generated # substring if it is # absent in the map. map[x[i:i + l]] = True for itr in map: # Printing all values in map. print(itr)# Driver codestr = "GeeksForGeeks"generateVowelSubstrings(str)# This code is contributed by shinjanpatra |
C#
/*package whatever //do not write package name here */// C# code to implement the above approachusing System;using System.Collections.Generic;class GFG { // Function to check if a character is vowel public static bool isVowel(char ch) { return (ch == 'a' || ch == 'A' || ch == 'e' || ch == 'E' || ch == 'i' || ch == 'I' || ch == 'o' || ch == 'O' || ch == 'u' || ch == 'U'); } // Function to check whether // string contains only vowel public static bool isValid(string s) { int n = s.Length; for (int i = 0; i < n; i++) { // Check if the character is // not vowel then invalid if (!isVowel(s[i])) return false; } return true; } // Function for generating unique substrings of vowels. public static void generateVowelSubstrings(string str) { Dictionary<string, bool> map = new Dictionary<string, bool>(); // Generate all subString of s for (int i = 0; i < str.Length; i++) { string temp = ""; for (int j = i; j < str.Length; j++) { temp += str[j]; // If temp contains only vowels if (isValid(temp)) { // store it only if substring is absent // in map. if (!map.ContainsKey(temp)) map[temp] = true; } } } foreach(KeyValuePair<string, bool> i in map) { // printing all unique substring. Console.WriteLine(i.Key); } } // Driver Code public static void Main(string[] args) { string str = "GeeksForGeeks"; generateVowelSubstrings(str); }}// This code is contributed by ukasp. |
Javascript
<script>// JavaScript code for the above approach// Function to check if a character is vowelfunction isvowel(ch){ return (ch == 'a' || ch == 'A' || ch == 'e' || ch == 'E' || ch == 'i' || ch == 'I' || ch == 'o' || ch == 'O' || ch == 'u' || ch == 'U');}// Function to check whether// string contains only vowelfunction isvalid(s){ let n = s.length; for(let i = 0; i < n; i++) { // Check if the character is // not vowel then invalid if (!isvowel(s[i])) return false; } return true;}// Function for generating all unique// substrings of only vowels.function generateVowelSubstrings(params) { let ans = 0; let map = {}; // Generate all substring of string for(let i = 0; i < params.length; i++) { let temp = ""; for(let j = i; j < params.length; j++) { temp += params[j]; // If temp contains only vowels if (isvalid(temp)) { map[temp] = true; } } } Object.keys(map).forEach(function (key) { document.write(key + '<br>'); });}// Driver codelet str = "GeeksForGeeks";generateVowelSubstrings(str);// This code is contributed by Potta Lokesh</script> |
Output
o e ee
Time Complexity: O(N3)
Auxiliary space: O(N)
Efficient Approach: A better approach to solve this problem is to extract all the maximum length substrings that contain only vowels. Now for all these sub-strings separately, generate unique sub-strings that contains only the vowels with the help of a map. Follow the steps mentioned below:
- Store all the maximum length substrings that contain only vowels(e.g For “Geeksaioer” maximum length one is “ee” and “aioe”).
- Use these substrings and generate the smaller segments from these substrings and use the map to find the unique ones.
- Print all the unique strings.
Below is the implementation of the above approach:
C++
// C++ code to implement above approach#include <bits/stdc++.h>using namespace std;// Function to check if a character is vowelbool isVowel(string c){ // Checking for vowels. return ((c == "a") || (c == "A") || (c == "e") || (c == "E") || (c == "i") || (c == "I") || (c == "o") || (c == "O") || (c == "u") || (c == "U"));}// Extracting all the maximum length// sub-strings that contain only vowels.unordered_map<string, bool> vowelSubstrings( string params){ string str; // Using map to remove identicals // substrings. e.g. AiotrfAio has 2 "Aio". unordered_map<string, bool> map; for (int i = 0; i < params.length(); i++) { string subString = params.substr(i, 1); if (isVowel(subString)) { str += subString; } else { // Storing a substring only if // it is not empty. if (!str.empty()) map[str] = true; str = ""; } } if (!str.empty()) map[str] = true; return map;}// Function to generate all unique substrings // containing only vowelsvoid generateVowelSubstrings(string params){ unordered_map<string, bool> substringMap = vowelSubstrings(params); unordered_map<string, bool> map; // map iterator. unordered_map<string, bool>::iterator itr; for (itr = substringMap.begin(); itr != substringMap.end(); ++itr) { string x = itr->first; // For each substring stored in map // generate all possible substrings. for (int i = 0; i < x.length(); i++) { for (int len = 1; len <= x.length() - i; len++) { // Storing the generated // substring if it is // absent in the map. map[x.substr(i, len)] = true; } } } for (itr = map.begin(); itr != map.end(); ++itr) { // Printing all values in map. cout << itr->first << '\n'; }}// Driver codeint main(){ string str = "GeeksForGeeks"; generateVowelSubstrings(str); return 0;} |
Java
/*package whatever //do not write package name here */// Java code to implement above approachimport java.io.*;import java.util.*;class GFG { // Function to check if a character is vowel public static boolean isVowel(String c) { // checking for vowels. return (c.equals("a") || c.equals("A") || c.equals("e") || c.equals("E") || c.equals("i") || c.equals("I") || c.equals("o") || c.equals("O") || c.equals("u") || c.equals("U")); } // extracting all the maximum length sub-strings that // contain only vowels. public static HashMap<String, Boolean> VowelSubstrings(String string) { String str = ""; // using map to remove identicals substrings. Ex :- // AiotrfAiopdvge(it has 2 "Aio"). HashMap<String, Boolean> map = new HashMap<>(); for (int i = 0; i < string.length(); i++) { String subStr = string.substring(i, (i + 1)); if (isVowel(subStr)) { str += subStr; } else { // storing a substring only if it is // present. if (!str.isEmpty()) map.putIfAbsent(str, true); str = ""; } } if (!str.isEmpty()) map.putIfAbsent(str, true); return map; } // Function to generate all unique substrings // containing only vowels public static void generateVowelSubstrings(String string) { HashMap<String, Boolean> substringMap = VowelSubstrings(string); HashMap<String, Boolean> map = new HashMap<>(); for (String key : substringMap.keySet()) { // for each key(substring) stored in map, we // generate all possible substrings. for (int i = 0; i < key.length(); i++) { for (int j = i + 1; j <= key.length(); j++) { // storing the generated substring if it // is absent in the map. map.putIfAbsent(key.substring(i, j), true); } } } for (String key : map.keySet()) { // printing all values in map. System.out.println(key); } } // Driver Code public static void main(String[] args) { String str = "GeeksForGeeks"; generateVowelSubstrings(str); }} |
Python3
# Python code to implement above approach# Function to check if a character is voweldef isVowel(c): # Checking for vowels. return ((c == "a") or (c == "A") or (c == "e") or (c == "E") or (c == "i") or (c == "I") or (c == "o") or (c == "O") or (c == "u") or (c == "U"))# Extracting all the maximum length# sub-Strings that contain only vowels.def vowelSubStrings(params): Str = "" # Using map to remove identicals # subStrings. e.g. AiotrfAio has 2 "Aio". map = dict() for i in range(len(params)): subString = params[i:i + 1] if (isVowel(subString)): Str += subString else: # Storing a subString only if # it is not empty. if (len(Str) > 0): map[Str] = True Str = "" if (len(Str) > 0): map[Str] = True return map# Function to generate all unique subStrings # containing only vowelsdef generateVowelSubStrings(params): subStringMap = vowelSubStrings(params) map = dict() # map iterator. for [key,val] in subStringMap.items(): x = key # For each subString stored in map # generate all possible subStrings. for i in range(len(x)): for Len in range(1,len(x) - i + 1): # Storing the generated # subString if it is # absent in the map. map[x[i: i+Len]] = True for [key,val] in map.items(): # Printing all values in map. print(key)# Driver codeStr = "GeeksForGeeks"generateVowelSubStrings(Str)# This code is contributed by shinjanpatra |
C#
/*package whatever //do not write package name here */// C# code to implement the above approachusing System;using System.Collections.Generic;public class GFG { // Function to check if a character is vowel public static bool isVowel(char ch) { return (ch == 'a' || ch == 'A' || ch == 'e' || ch == 'E' || ch == 'i' || ch == 'I' || ch == 'o' || ch == 'O' || ch == 'u' || ch == 'U'); } // Function to check whether // string contains only vowel public static bool isValid(string s) { int n = s.Length; for (int i = 0; i < n; i++) { // Check if the character is // not vowel then invalid if (!isVowel(s[i])) return false; } return true; } // Function for generating unique substrings of vowels. public static void generateVowelSubstrings(string str) { Dictionary<string, bool> map = new Dictionary<string, bool>(); // Generate all subString of s for (int i = 0; i < str.Length; i++) { string temp = ""; for (int j = i; j < str.Length; j++) { temp += str[j]; // If temp contains only vowels if (isValid(temp)) { // store it only if substring is absent // in map. if (!map.ContainsKey(temp)) map[temp] = true; } } } foreach(String i in map.Keys) { // printing all unique substring. Console.WriteLine(i); } } // Driver Code public static void Main(string[] args) { string str = "GeeksForGeeks"; generateVowelSubstrings(str); }}// This code is contributed by gauravrajput1 |
Javascript
<script> // JavaScript code to implement above approach // Function to check if a character is vowel const isVowel = (c) => { // Checking for vowels. return ((c == "a") || (c == "A") || (c == "e") || (c == "E") || (c == "i") || (c == "I") || (c == "o") || (c == "O") || (c == "u") || (c == "U")); } // Extracting all the maximum length // sub-strings that contain only vowels. const vowelSubstrings = (params) => { let str = ""; // Using map to remove identicals // substrings. e.g. AiotrfAio has 2 "Aio". let map = {}; for (let i = 0; i < params.length; i++) { let subString = params.substring(i, i + 1); if (isVowel(subString)) { str += subString; } else { // Storing a substring only if // it is not empty. if (str.length !== 0) map[str] = true; str = ""; } } if (str.length !== 0) map[str] = true; return map; } // Function to generate all unique substrings // containing only vowels const generateVowelSubstrings = (params) => { let substringMap = vowelSubstrings(params); let map = {}; // map iterator. for (let itr in substringMap) { let x = itr; // For each substring stored in map // generate all possible substrings. for (let i = 0; i < x.length; i++) { for (let len = 1; len <= x.length - i; len++) { // Storing the generated // substring if it is // absent in the map. map[x.substring(i, i + len)] = true; } } } for (let itr in map) { // Printing all values in map. document.write(`${itr}<br/>`); } } // Driver code let str = "GeeksForGeeks"; generateVowelSubstrings(str);// This code is contributed by rakeshsahni</script> |
Output
o ee e
Time Complexity: O(N2)
Auxiliary Space: O(N)
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!
