Dada la string str que contiene letras mayúsculas y minúsculas y un número entero K . La tarea es encontrar el recuento de substrings que contengan exactamente K vocales (tal vez repetitivas).
Ejemplos:
Entrada: str = “aeiou”, K = 2
Salida: 4
Explicación: Las substrings son “ae”, “ei”, “io”, “ou”.Entrada: str = “TrueGeek”, K = 3
Salida: 5
Explicación: Todas las substrings posibles son:
“TrueGe”, “rueGe”, “ueGe”, “eGee”, “eGeek”.
Enfoque: La solución de este problema se basa en un enfoque codicioso . Genere todas las substrings y para cada substring verifique el conteo de vocales. Siga los pasos que se mencionan a continuación.
- Genere todas las substrings . Para cada substring, haga lo siguiente
- Almacena el recuento de ocurrencias de vocales .
- Compruebe si un nuevo carácter en la substring es una vocal o no.
- Si es una vocal, incrementa el número de vocales encontradas
- Ahora, para cada substring, si el conteo de vocales es K , incremente el conteo final.
- Devuelve el recuento final como la respuesta requerida al final.
A continuación se muestra la implementación del código anterior.
C++
// C++ code to implement above approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 128
// Function to check whether
// a character is vowel or not
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 count of
// substring with k vowels
int get(string str, int k)
{
int n = str.length();
// Stores the count of
// substring with K vowels
int ans = 0;
// Consider all substrings
// beginning with str[i]
for (int i = 0; i < n; i++) {
int count = 0;
// Consider all substrings
// between [i, j]
for (int j = i; j < n; j++) {
// If this is a vowel, for this
// substring, increment count.
if (isVowel(str[j])) {
count++;
}
// If vowel count becomes k,
// then increment final count.
if (count == k) {
ans++;
}
if (count > k)
break;
}
}
return ans;
}
// Driver code
int main(void)
{
string s = "aeiou";
int K = 2;
cout << get(s, K);
return 0;
}
Java
// Java code to implement above approach
class GFG
{
static final int MAX = 128;
// 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 count of
// subString with k vowels
static int get(String str, int k)
{
int n = str.length();
// Stores the count of
// subString with K vowels
int ans = 0;
// Consider all subStrings
// beginning with str[i]
for (int i = 0; i < n; i++) {
int count = 0;
// Consider all subStrings
// between [i, j]
for (int j = i; j < n; j++) {
// If this is a vowel, for this
// subString, increment count.
if (isVowel(str.charAt(j))) {
count++;
}
// If vowel count becomes k,
// then increment final count.
if (count == k) {
ans++;
}
if (count > k)
break;
}
}
return ans;
}
// Driver code
public static void main(String[] args)
{
String s = "aeiou";
int K = 2;
System.out.print(get(s, K));
}
}
// This code is contributed by 29AjayKumar
Python3
# python code to implement above approach MAX = 128 # Function to check whether # a character is vowel or not def 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 count of # substring with k vowels def get(str, k): n = len(str) # Stores the count of # substring with K vowels ans = 0 # Consider all substrings # beginning with str[i] for i in range(0, n): count = 0 # Consider all substrings # between [i, j] for j in range(i, n): # If this is a vowel, for this # substring, increment count. if (isVowel(str[j])): count += 1 # If vowel count becomes k, # then increment final count. if (count == k): ans += 1 if (count > k): break return ans # Driver code if __name__ == "__main__": s = "aeiou" K = 2 print(get(s, K)) # This code is contributed by rakeshsahni
C#
// C# code to implement above approach
using System;
class GFG {
// 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 count of
// substring with k vowels
static int get(string str, int k)
{
int n = str.Length;
// Stores the count of
// substring with K vowels
int ans = 0;
// Consider all substrings
// beginning with str[i]
for (int i = 0; i < n; i++) {
int count = 0;
// Consider all substrings
// between [i, j]
for (int j = i; j < n; j++) {
// If this is a vowel, for this
// substring, increment count.
if (isVowel(str[j])) {
count++;
}
// If vowel count becomes k,
// then increment final count.
if (count == k) {
ans++;
}
if (count > k)
break;
}
}
return ans;
}
// Driver code
public static void Main()
{
string s = "aeiou";
int K = 2;
Console.WriteLine(get(s, K));
}
}
// This code is contributed by ukasp.
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 count of
// substring with k vowels
function get(str, k) {
let n = str.length;
// Stores the count of
// substring with K vowels
let ans = 0;
// Consider all substrings
// beginning with str[i]
for (let i = 0; i < n; i++) {
let count = 0;
// Consider all substrings
// between [i, j]
for (let j = i; j < n; j++) {
// If this is a vowel, for this
// substring, increment count.
if (isVowel(str[j])) {
count++;
}
// If vowel count becomes k,
// then increment final count.
if (count == k) {
ans++;
}
if (count > k)
break;
}
}
return ans;
}
// Driver code
let s = "aeiou";
let K = 2;
document.write(get(s, K));
// This code is contributed by Potta Lokesh
</script>
Producción
4
Complejidad de tiempo: O(N 2 ) donde N es la longitud de la string.
Espacio Auxiliar: O(1)