Dada la string str de N caracteres que contienen alfabetos ingleses tanto en mayúsculas como en minúsculas, la tarea es encontrar el recuento de substrings de tamaño K que contienen exactamente X vocales .
Ejemplos:
Entrada: str = «GeeksForGeeks», K = 2, X = 2
Salida: 2
Explicación: La string dada solo contiene 2 substrings de tamaño 2 que consisten en 2 vocales. Son «ee» y «ee».Entrada: str = «TrueGeek», K = 3, X = 2
Salida: 5
Enfoque: El problema dado se puede resolver usando una técnica de ventana deslizante manteniendo una ventana de tamaño K y siguiendo la pista del número de vocales encontradas en la ventana actual. Si el conteo de vocales en la ventana actual es igual a X , incremente el conteo final requerido en 1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the 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
// K-sized substring having X vowels
int cntSubstr(string str, int K, int X)
{
// Stores the number of vowels
// in the current window
int vow = 0;
for (int i = 0; i < K; i++)
if (isVowel(str[i]))
vow++;
// Stores the count of K length
// substring with X vowels
int ans = vow == X ? 1 : 0;
for (int i = 1; i < str.length(); i++) {
// Remove (i - 1)th character
// from the current window
vow = isVowel(str[i - 1]) ? vow - 1 : vow;
// Insert (i - 1 + K)th character
// from the current window
vow = isVowel(str[i - 1 + K]) ? vow + 1 : vow;
if (vow == X)
// Increment answer
ans++;
}
// Return Answer
return ans;
}
// Driver code
int main(void)
{
string s = "TrueGeek";
int K = 3, X = 2;
cout << cntSubstr(s, K, X);
return 0;
}
Java
// Java code to implement the above approach
import java.io.*;
class 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 count of
// K-sized subString having X vowels
static int cntSubstr(String str, int K, int X)
{
// Stores the number of vowels
// in the current window
int vow = 0;
for (int i = 0; i < K; i++)
if (isVowel(str.charAt(i)))
vow++;
// Stores the count of K length()
// subString with X vowels
int ans = vow == X ? 1 : 0;
for (int i = 1; i < str.length(); i++) {
// Remove (i - 1)th character
// from the current window
vow = isVowel(str.charAt(i - 1)) ? vow - 1 : vow;
// Insert (i - 1 + K)th character
// from the current window
if(i - 1 + K < str.length())
vow = isVowel(str.charAt(i - 1 + K)) ? vow + 1 : vow;
if (vow == X)
// Increment answer
ans++;
}
// Return Answer
return ans;
}
// Driver code
public static void main (String[] args) {
String s = "TrueGeek";
int K = 3, X = 2;
System.out.println(cntSubstr(s, K, X));
}
}
// This code is contributed by Shubham Singh
Python3
# Python3 program of the 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 # K-sized substring having X vowels def cntSubstr(str, K, X): # Stores the number of vowels # in the current window vow = 0 for i in range(0, K): if (isVowel(str[i])): vow += 1 # Stores the count of K length # substring with X vowels ans = 1 if vow == X else 0 for i in range(1, len(str) - K + 1): # Remove (i - 1)th character # from the current window vow = vow - 1 if isVowel(str[i - 1]) else vow # Insert (i - 1 + K)th character # from the current window vow = vow + 1 if isVowel(str[i - 1 + K]) else vow if (vow == X): # Increment answer ans += 1 # Return Answer return ans # Driver code if __name__ == "__main__": s = "TrueGeek" K, X = 3, 2 print(cntSubstr(s, K, X)) # This code is contributed by rakeshsahni
C#
// C# code to implement the 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
// K-sized substring having X vowels
static int cntSubstr(string str, int K, int X)
{
// Stores the number of vowels
// in the current window
int vow = 0;
for (int i = 0; i < K; i++)
if (isVowel(str[i]))
vow++;
// Stores the count of K length
// substring with X vowels
int ans = vow == X ? 1 : 0;
for (int i = 1; i < str.Length; i++) {
// Remove (i - 1)th character
// from the current window
vow = isVowel(str[i - 1]) ? vow - 1 : vow;
// Insert (i - 1 + K)th character
// from the current window
if(i - 1 + K < str.Length)
vow = isVowel(str[i - 1 + K]) ? vow + 1 : vow;
if (vow == X)
// Increment answer
ans++;
}
// Return Answer
return ans;
}
// Driver code
public static void Main()
{
string s = "TrueGeek";
int K = 3, X = 2;
Console.Write(cntSubstr(s, K, X));
}
}
// 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 count of
// K-sized substring having X vowels
function cntSubstr(str, K, X)
{
// Stores the number of vowels
// in the current window
let vow = 0;
for (let i = 0; i < K; i++)
if (isVowel(str[i]))
vow++;
// Stores the count of K length
// substring with X vowels
let ans = vow == X ? 1 : 0;
for (let i = 1; i < str.length; i++) {
// Remove (i - 1)th character
// from the current window
vow = isVowel(str[i - 1]) ? vow - 1 : vow;
// Insert (i - 1 + K)th character
// from the current window
vow = isVowel(str[i - 1 + K]) ? vow + 1 : vow;
if (vow == X)
// Increment answer
ans++;
}
// Return Answer
return ans;
}
// Driver code
let s = "TrueGeek";
let K = 3, X = 2;
document.write(cntSubstr(s, K, X));
// This code is contributed by Potta Lokesh
</script>
Producción
5
Complejidad temporal: O(N)
Espacio auxiliar: O(1)