La substring más larga que contiene exactamente K vocales

Dada la string str que contiene letras mayúsculas y minúsculas y un número entero K . La tarea es encontrar la substring más larga que contenga exactamente K vocales (tal vez repetitivas).

Ejemplos:

Entrada: GeeksForGeeks, K = 2
Salida: 7, eksForG
Explicación: La substring más larga que tiene exactamente dos vocales es “eksForG”.

Entrada: TrueGeek, K = 3
Salida: 6, TrueGe

Enfoque : la tarea se puede resolver haciendo un seguimiento del número de vocales encontradas en la ventana actual .
Siga los pasos a continuación para resolver el problema:

• Cree una variable ‘ voto ‘ para realizar un seguimiento del número de vocales en la ventana actual
• Comience a aumentar el tamaño de la ventana. Si el voto se vuelve mayor que K , comience a reducir la ventana desde el frente.
• Maximiza el tamaño de la ventana en cada paso

A continuación se muestra la implementación del enfoque anterior:

// 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 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 length of the longest
// substring with k vowels
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 = 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 code
int main(void)
{
    string s = "TrueGeek";
    int K = 3;
    get(s, K);
    return 0;
}

// Java code to implement above approach
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 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.

# Python code for 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 length of the longest
# substring with k vowels
def 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 code
s = "TrueGeek"
K = 3
get(s, K)
 
# This code is contributed by Saurabh Jaiswal

// 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 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[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 code
public static void Main()
{
    string s = "TrueGeek";
    int K = 3;
    get(s, K);
     
}
}
 
// This code is contributed by Samim Hossain Mondal.

<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>

6 TrueGe

Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)