Dada la string str de longitud N que contiene letras mayúsculas y minúsculas y un número entero K . La tarea es encontrar todas las substrings que contengan exactamente K vocales distintas .
Ejemplos:
Entrada: str = “aeiou”, K = 2
Salida: “ae”, “ei”, “io”, “ou”
Explicación: Estas son las substrings que contienen exactamente 2 vocales distintas.Entrada: str = «TrueGeek», K = 3
Salida: «»
Explicación: aunque la string tiene más de 3 vocales, no hay tres vocales únicas.
Así que la respuesta está vacía.Entrada: str = “TrueGoik”, K = 3
Salida: “TrueGo”, “rueGo”, “ueGo”, “eGoi”, “eGoik”
Enfoque: este problema se puede resolver mediante un enfoque codicioso . Genere las substrings y verifique cada substring. Siga los pasos que se mencionan a continuación para resolver el problema:
- Primero genere todas las substrings a partir de cada índice i en el rango 0 a N .
- Entonces para cada substring:
- Mantenga una array hash para almacenar las ocurrencias de vocales únicas.
- Compruebe si un nuevo carácter en la substring es una vocal o no.
- Si es una vocal, incremente su ocurrencia en el hash y mantenga un conteo de vocales distintas encontradas
- Ahora, para cada substring, si el recuento distinto de vocales es K , imprima la substring.
- Si para cualquier ciclo para encontrar substrings que comiencen desde i , el recuento de vocales distintas excede K , o si la longitud de la substring ha alcanzado la longitud de la string, rompa el ciclo y busque substrings que comiencen desde i+1 .
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to find all substrings with
// exactly k distinct vowels
#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');
}
int getIndex(char ch)
{
return (ch - 'A' > 26 ?
ch - 'a' : ch - 'A');
}
// Function to find all substrings
// with exactly k unique vowels
void countkDist(string str, int k)
{
int n = str.length();
// Consider all substrings
// beginning with str[i]
for (int i = 0; i < n; i++) {
int dist_count = 0;
// To store count of characters
// from 'a' to 'z'
vector<int> cnt(26, 0);
// Consider all substrings
// between str[i..j]
for (int j = i; j < n; j++) {
// If this is a new vowel
// for this substring,
// increment dist_count.
if (isVowel(str[j])
&& cnt[getIndex(str[j])] == 0) {
dist_count++;
}
// Increment count of
// current character
cnt[getIndex(str[j])]++;
// If distinct vowels count
// becomes k, then print the
// substring.
if (dist_count == k) {
cout << str.substr(i, j - i + 1) << endl;
}
if (dist_count > k)
break;
}
}
}
// Driver code
int main()
{
string str = "TrueGoik";
int K = 3;
countkDist(str, K);
return 0;
}
Java
// Java program to find all subStrings with
// exactly k distinct vowels
import java.util.*;
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');
}
static int getIndex(char ch)
{
return (ch - 'A' > 26 ?
ch - 'a' : ch - 'A');
}
// Function to find all subStrings
// with exactly k unique vowels
static void countkDist(String str, int k)
{
int n = str.length();
// Consider all subStrings
// beginning with str[i]
for (int i = 0; i < n; i++) {
int dist_count = 0;
// To store count of characters
// from 'a' to 'z'
int[] cnt = new int[26];
// Consider all subStrings
// between str[i..j]
for (int j = i; j < n; j++) {
String print = new String(str);
// If this is a new vowel
// for this subString,
// increment dist_count.
if (isVowel(str.charAt(j))
&& cnt[getIndex(str.charAt(j))] == 0) {
dist_count++;
}
// Increment count of
// current character
cnt[getIndex(str.charAt(j))]++;
// If distinct vowels count
// becomes k, then print the
// subString.
if (dist_count == k) {
System.out.print(print.substring(i, j +1) +"\n");
}
if (dist_count > k)
break;
}
}
}
// Driver code
public static void main(String[] args)
{
String str = "TrueGoik";
int K = 3;
countkDist(str, K);
}
}
// This code is contributed by Rajput-Ji
Python3
# python3 program to find all substrings with
# exactly k distinct vowels
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')
def getIndex(ch):
if ord(ch) - ord('A') > 26:
return ord(ch) - ord('a')
else:
return ord(ch) - ord('A')
# Function to find all substrings
# with exactly k unique vowels
def countkDist(str, k):
n = len(str)
# Consider all substrings
# beginning with str[i]
for i in range(0, n):
dist_count = 0
# To store count of characters
# from 'a' to 'z'
cnt = [0 for _ in range(26)]
# Consider all substrings
# between str[i..j]
for j in range(i, n):
# If this is a new vowel
# for this substring,
# increment dist_count.
if (isVowel(str[j])
and cnt[getIndex(str[j])] == 0):
dist_count += 1
# Increment count of
# current character
cnt[getIndex(str[j])] += 1
# If distinct vowels count
# becomes k, then print the
# substring.
if (dist_count == k):
print(str[i:i+j - i + 1])
if (dist_count > k):
break
# Driver code
if __name__ == "__main__":
str = "TrueGoik"
K = 3
countkDist(str, K)
# This code is contributed by rakeshsahni
C#
// C# program to find all substrings with
// exactly k distinct vowels
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');
}
static int getIndex(char ch)
{
return (ch - 'A' > 26 ? ch - 'a' : ch - 'A');
}
// Function to find all substrings
// with exactly k unique vowels
static void countkDist(string str, int k)
{
int n = str.Length;
// Consider all substrings
// beginning with str[i]
for (int i = 0; i < n; i++) {
int dist_count = 0;
// To store count of characters
// from 'a' to 'z'
int[] cnt = new int[26];
// Consider all substrings
// between str[i..j]
for (int j = i; j < n; j++) {
// If this is a new vowel
// for this substring,
// increment dist_count.
if (isVowel(str[j])
&& cnt[getIndex(str[j])] == 0) {
dist_count++;
}
// Increment count of
// current character
cnt[getIndex(str[j])]++;
// If distinct vowels count
// becomes k, then print the
// substring.
if (dist_count == k) {
Console.WriteLine(
str.Substring(i, j - i + 1));
}
if (dist_count > k)
break;
}
}
}
// Driver code
public static void Main()
{
string str = "TrueGoik";
int K = 3;
countkDist(str, K);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript code for the above approach
// 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 getIndex(ch) {
return ((ch.charCodeAt(0) - 'A'.charCodeAt(0)) > 26 ? (ch.charCodeAt(0) - 'a'.charCodeAt(0)) :
(ch.charCodeAt(0) - 'A'.charCodeAt(0)));
}
// Function to find all substrings
// with exactly k unique vowels
function countkDist(str, k) {
let n = str.length;
// Consider all substrings
// beginning with str[i]
for (let i = 0; i < n; i++) {
let dist_count = 0;
// To store count of characters
// from 'a' to 'z'
let cnt = new Array(26).fill(0);
// Consider all substrings
// between str[i..j]
for (let j = i; j < n; j++) {
// If this is a new vowel
// for this substring,
// increment dist_count.
if (isVowel(str[j])
&& cnt[getIndex(str[j])] == 0) {
dist_count++;
}
// Increment count of
// current character
cnt[getIndex(str[j])]++;
// If distinct vowels count
// becomes k, then print the
// substring.
if (dist_count == k) {
document.write(str.slice(i, i + j - i + 1) + '<br>');
}
if (dist_count > k)
break;
}
}
}
// Driver code
let s = "TrueGoik";
let K = 3
countkDist(s, K);
// This code is contributed by Potta Lokesh
</script>
Producción
TrueGo rueGo ueGo eGoi eGoik
Complejidad de tiempo: O(N 2 )
Espacio auxiliar: O(N 2 ) para almacenar las substrings resultantes