Given string str containing both uppercase and lowercase letters, and an integer K. The task is to find the longest substring containing exactly K vowels (maybe repetitive).
Examples:
Input: GeeksForGeeks, K = 2
Output: 7, eksForG
Explanation: The longest substring having exactly two vowels is “eksForG”.Input: TrueGeek, K = 3
Output: 6, TrueGe
Brute Force Approach: The brute force approach for finding the longest substring with exactly K vowels would be to generate all possible substrings of the given string and for each substring, count the number of vowels it contains. If a substring contains exactly K vowels and its length is greater than the length of the previously found substring with K vowels, update the answer.
Steps to implement the approach:
- Define a function isVowel(char x) which takes a character as an input and returns true if it is a vowel, otherwise false.
- Define a function get(string s, int k) which takes a string s and an integer k as inputs and returns nothing.
- Initialize a variable ans to -1 and a string variable res to an empty string.
- Use two nested for loops to iterate through all the substrings of the string s.
- Within the inner loop, initialize a variable vow to 0, and iterate through the substring to count the number of vowels.
- If the number of vowels equals k and the length of the substring is greater than ans, update ans to the length of the substring and res to the substring itself.
- Print ans and res.
- In the main function, initialize a string s and an integer K to test the get function.
- Call the get function with s and K as inputs.
Implementation of the above algorithm:
C++
// C++ program to find the longest// substring with exactly K vowels.#include <bits/stdc++.h>using namespace std;#define MAX 128// Function to check whether// a character is vowel or notbool isVowel(char x){ return (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u' || x == 'A' || x == 'E' || x == 'I' || x == 'O' || x == 'U');}// Function to find the length of the longest// substring with k vowelsvoid get(string s, int k){ int ans = -1; string res; for (int i = 0; i < s.length(); i++) { for (int j = i; j < s.length(); j++) { int vow = 0; for (int l = i; l <= j; l++) { if (isVowel(s[l])) vow++; } if (vow == k && j - i + 1 > ans) { ans = j - i + 1; res = s.substr(i, j - i + 1); } } } cout << ans << " " << res;}// Driver codeint main(void){ string s = "TrueGeek"; int K = 3; get(s, K); return 0;} |
Java
// Java program to find the longest// substring with exactly K vowels.import java.util.*;public class Main { public static final int MAX = 128; // Function to check whether // a character is vowel or not public static boolean isVowel(char x) { return (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u' || x == 'A' || x == 'E' || x == 'I' || x == 'O' || x == 'U'); } // Function to find the length of the longest // substring with k vowels public static void get(String s, int k) { int ans = -1; String res = ""; for (int i = 0; i < s.length(); i++) { for (int j = i; j < s.length(); j++) { int vow = 0; for (int l = i; l <= j; l++) { if (isVowel(s.charAt(l))) vow++; } if (vow == k && j - i + 1 > ans) { ans = j - i + 1; res = s.substring(i, j + 1); } } } System.out.println(ans + " " + res); } // Driver code public static void main(String[] args) { String s = "TrueGeek"; int K = 3; get(s, K); }} |
Python3
# python3 program to find the longest# substring with exactly K vowels.# Converted to Python3def isVowel(x): # Function to check whether # a character is vowel or not return (x == 'a' or x == 'e' or x == 'i' or x == 'o' or x == 'u' or x == 'A' or x == 'E' or x == 'I' or x == 'O' or x == 'U')def get(s, k): # Function to find the length of the longest # substring with k vowels ans = -1 res = "" for i in range(len(s)): for j in range(i, len(s)): vow = 0 for l in range(i, j+1): if isVowel(s[l]): vow += 1 if vow == k and j - i + 1 > ans: ans = j - i + 1 res = s[i:j+1] print(ans, res)s = "TrueGeek"K = 3get(s, K) |
C#
// C# program to find the longest// substring with exactly K vowels.using System;class MainClass { // Function to check whether // a character is vowel or not static bool isVowel(char x) { return (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u' || x == 'A' || x == 'E' || x == 'I' || x == 'O' || x == 'U'); } // Function to find the length of the longest // substring with k vowels static void get(string s, int k) { int ans = -1; string res = ""; for (int i = 0; i < s.Length; i++) { for (int j = i; j < s.Length; j++) { int vow = 0; for (int l = i; l <= j; l++) { if (isVowel(s[l])) vow++; } if (vow == k && j - i + 1 > ans) { ans = j - i + 1; res = s.Substring(i, j - i + 1); } } } Console.WriteLine(ans + " " + res); } // Driver code static void Main(string[] args) { string s = "TrueGeek"; int K = 3; get(s, K); }} |
Javascript
// JavaScript program to find the longest// substring with exactly K vowels.// Function to check whether// a character is vowel or notfunction isVowel(x) { return (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u' || x == 'A' || x == 'E' || x == 'I' || x == 'O' || x == 'U');}// Function to find the length of the longest// substring with k vowelsfunction get(s, k) { let ans = -1; let res = ""; for (let i = 0; i < s.length; i++) { for (let j = i; j < s.length; j++) { let vow = 0; for (let l = i; l <= j; l++) { if (isVowel(s.charAt(l))) vow++; } if (vow == k && j - i + 1 > ans) { ans = j - i + 1; res = s.substring(i, j + 1); } } } console.log(ans + " " + res);}// Driver codelet s = "TrueGeek";let K = 3;get(s, K); |
Output :
6 TrueGe
Time Complexity: O(N3), where n is the length of the string s. This is because of the three nested loops in the get function.
Space Complexity: O(1)
Sliding Window Approach: The task can be solved by keeping track of the number of vowels encountered in the current window.
Follow the below steps to solve the problem:
- Create a variable ‘vow‘ to keep track of the number of vowels in the current window
- Start increasing the size of the window, If vow becomes greater than K, start shrinking the window from the front.
- Maximize the size of the window in each step
Below is the implementation of the above approach:
C++14
// C++ program to find the longest// substring with exactly K vowels.#include <bits/stdc++.h>using namespace std;#define MAX 128// Function to check whether// a character is vowel or notbool isVowel(char x){ return (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u' || x == 'A' || x == 'E' || x == 'I' || x == 'O' || x == 'U');}// Function to find the length of the longest// substring with k vowelsvoid get(string s, int k){ // Stores the length of longest // substring with K vowels int ans = -1; // Stores the number of vowels // in the current window int vow = 0; // Stores the resultant string string res; int l = 0, r = 0; while (r < s.length()) { if (isVowel(s[r])) vow++; if (vow == k) { if (ans < r - l + 1) { ans = max(ans, r - l + 1); res = s.substr(l, r - l + 1); } } if (vow > k) { while (vow > k) { if (isVowel(s[l])) vow--; l++; } if (ans < r - l + 1) { ans = max(ans, r - l + 1); res = s.substr(l, r - l + 1); } } r++; } cout << ans << " " << res;}// Driver codeint main(void){ string s = "TrueGeek"; int K = 3; get(s, K); return 0;} |
Java
// Java code to implement above approachclass GFG { // Function to check whether // a character is vowel or not static boolean isVowel(char x) { return (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u' || x == 'A' || x == 'E' || x == 'I' || x == 'O' || x == 'U'); } // Function to find the length of the longest // substring with k vowels static void get(String s, int k) { // Stores the length of longest // substring with K vowels int ans = -1; // Stores the number of vowels // in the current window int vow = 0; // Stores the resultant string String res = ""; int l = 0, r = 0; while (r < s.length()) { if (isVowel(s.charAt(r))) vow++; if (vow == k) { if (ans < r - l + 1) { ans = Math.max(ans, r - l + 1); res = s.substring(l, r - l + 1); } } if (vow > k) { while (vow > k) { if (isVowel(s.charAt(l))) vow--; l++; } if (ans < r - l + 1) { ans = Math.max(ans, r - l + 1); res = s.substring(l, r - l + 1); } } r++; } System.out.print(ans + " " + res); } // Driver code public static void main(String[] args) { String s = "TrueGeek"; int K = 3; get(s, K); }}// This code is contributed by ukasp. |
Python3
# Python code for the above approachMAX = 128# Function to check whether# a character is vowel or notdef isVowel(x): return (x == 'a' or x == 'e' or x == 'i' or x == 'o' or x == 'u' or x == 'A' or x == 'E' or x == 'I' or x == 'O' or x == 'U')# Function to find the length of the longest# substring with k vowelsdef get(s, k): # Stores the length of longest # substring with K vowels ans = -1 # Stores the number of vowels # in the current window vow = 0 # Stores the resultant string res = None l = 0 r = 0 while (r < len(s)): if (isVowel(s[r])): vow += 1 if (vow == k): if (ans < r - l + 1): ans = max(ans, r - l + 1) res = s[l:(r - l + 1)] if (vow > k): while (vow > k): if (isVowel(s[l])): vow -= 1 l += 1 if (ans < r - l + 1): ans = max(ans, r - l + 1) res = s[l: (r - l + 1)] r += 1 print(f"{ans} {res}")# Driver codes = "TrueGeek"K = 3get(s, K)# This code is contributed by Saurabh Jaiswal |
C#
// C# code to implement above approachusing System;class GFG{ // Function to check whether// a character is vowel or notstatic bool isVowel(char x){ return (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u' || x == 'A' || x == 'E' || x == 'I' || x == 'O' || x == 'U');}// Function to find the length of the longest// substring with k vowelsstatic void get(string s, int k){ // Stores the length of longest // substring with K vowels int ans = -1; // Stores the number of vowels // in the current window int vow = 0; // Stores the resultant string string res = ""; int l = 0, r = 0; while (r < s.Length) { if (isVowel(s[r])) vow++; if (vow == k) { if (ans < r - l + 1) { ans = Math.Max(ans, r - l + 1); res = s.Substring(l, r - l + 1); } } if (vow > k) { while (vow > k) { if (isVowel(s[l])) vow--; l++; } if (ans < r - l + 1) { ans = Math.Max(ans, r - l + 1); res = s.Substring(l, r - l + 1); } } r++; } Console.Write(ans + " " + res);}// Driver codepublic static void Main(){ string s = "TrueGeek"; int K = 3; get(s, K); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript code for the above approach let MAX = 128 // Function to check whether // a character is vowel or not function isVowel(x) { return (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u' || x == 'A' || x == 'E' || x == 'I' || x == 'O' || x == 'U'); } // Function to find the length of the longest // substring with k vowels function get(s, k) { // Stores the length of longest // substring with K vowels let ans = -1; // Stores the number of vowels // in the current window let vow = 0; // Stores the resultant string let res; let l = 0, r = 0; while (r < s.length) { if (isVowel(s[r])) vow++; if (vow == k) { if (ans < r - l + 1) { ans = Math.max(ans, r - l + 1); res = s.slice(l, r - l + 1); } } if (vow > k) { while (vow > k) { if (isVowel(s[l])) vow--; l++; } if (ans < r - l + 1) { ans = Math.max(ans, r - l + 1); res = s.slice(l, r - l + 1); } } r++; } document.write(ans + " " + res); } // Driver code let s = "TrueGeek"; let K = 3; get(s, K); // This code is contributed by Potta Lokesh </script> |
Output
6 TrueGe
Time Complexity: O(N)
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!
