Dada una string S , la tarea es verificar si la string se puede dividir en dos substrings de modo que el número de vocales en ambas sea igual. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: S = «geeks»
Salida: Sí
Explicación: Dividir las strings en substrings «ge» ( cantidad de vocales = 1 ) y «eks» ( cantidad de vocales = 1 ) cumple la condición.Entrada: S = «libro de texto»
Salida: No
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar la string S dada y dividir la string en dos substrings en cada índice posible. Para cada división, verifique si las dos substrings tienen el mismo número de vocales presentes o no. Si se encuentra que es cierto, escriba «Sí»; de lo contrario, escriba «No» .
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar calculando previamente el número total de vocales en la string. Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos totalVowels y vocalsTillNow , para almacenar el número total de vocales y el recuento actual de vocales, respectivamente.
- Ahora recorra la string S y cuente todas las vocales y guárdelas en totalVowels .
- Ahora, nuevamente atraviese la string S y disminuya totalVowels en 1 e incremente vocalsTillNow en 1 , si ocurre una vocal. Compruebe si totalVowels se vuelve igual a vocalsTillNow en algún momento o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if any
// character is a vowel or not
bool isVowel(char ch)
{
// Lowercase vowels
if (ch == 'a' || ch == 'e' || ch == 'i'
|| ch == 'o' || ch == 'u')
return true;
// Uppercase vowels
if (ch == 'A' || ch == 'E' || ch == 'I'
|| ch == 'O' || ch == 'U')
return true;
// Otherwise
return false;
}
// Function to check if string S
// can be split into two substrings
// with equal number of vowels
string containsEqualStrings(string S)
{
// Stores the count of vowels
// in the string S
int totalVowels = 0;
// Traverse over the string
for (int i = 0;
i < S.size(); i++)
{
// If S[i] is vowel
if (isVowel(S[i]))
totalVowels++;
}
// Stores the count of vowels
// upto the current index
int vowelsTillNow = 0;
// Traverse over the string
for (int i = 0;
i < S.size(); i++)
{
// If S[i] is vowel
if (isVowel(S[i]))
{
vowelsTillNow++;
totalVowels--;
// If vowelsTillNow and
// totalVowels are equal
if (vowelsTillNow
== totalVowels)
{
return "Yes";
}
}
}
// Otherwise
return "No";
}
// Driver Code
int main()
{
string S = "geeks";
cout<<(containsEqualStrings(S));
}
// This code is contributed by mohit kumar 29.
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to check if any
// character is a vowel or not
public static boolean isVowel(char ch)
{
// Lowercase vowels
if (ch == 'a' || ch == 'e' || ch == 'i'
|| ch == 'o' || ch == 'u')
return true;
// Uppercase vowels
if (ch == 'A' || ch == 'E' || ch == 'I'
|| ch == 'O' || ch == 'U')
return true;
// Otherwise
return false;
}
// Function to check if string S
// can be split into two substrings
// with equal number of vowels
public static String
containsEqualStrings(String S)
{
// Stores the count of vowels
// in the string S
int totalVowels = 0;
// Traverse over the string
for (int i = 0;
i < S.length(); i++) {
// If S[i] is vowel
if (isVowel(S.charAt(i)))
totalVowels++;
}
// Stores the count of vowels
// upto the current index
int vowelsTillNow = 0;
// Traverse over the string
for (int i = 0;
i < S.length(); i++) {
// If S[i] is vowel
if (isVowel(S.charAt(i))) {
vowelsTillNow++;
totalVowels--;
// If vowelsTillNow and
// totalVowels are equal
if (vowelsTillNow
== totalVowels) {
return "Yes";
}
}
}
// Otherwise
return "No";
}
// Driver Code
public static void main(String[] args)
{
String S = "geeks";
System.out.println(
containsEqualStrings(S));
}
}
Python3
# Python3 program for the above approach # Function to check if any # character is a vowel or not def isVowel(ch): # Lowercase vowels if (ch == 'a' or ch == 'e' or ch == 'i' or ch == 'o' or ch == 'u'): return True # Uppercase vowels if (ch == 'A' or ch == 'E' or ch == 'I' or ch == 'O' or ch == 'U'): return True # Otherwise return False # Function to check if string S # can be split into two substrings # with equal number of vowels def containsEqualStrings(S): # Stores the count of vowels # in the string S totalVowels = 0 # Traverse over the string for i in range(len(S)): # If S[i] is vowel if (isVowel(S[i])): totalVowels += 1 # Stores the count of vowels # upto the current index vowelsTillNow = 0 # Traverse over the string for i in range(len(S)): # If S[i] is vowel if (isVowel(S[i])): vowelsTillNow += 1 totalVowels -= 1 # If vowelsTillNow and # totalVowels are equal if (vowelsTillNow == totalVowels): return "Yes" # Otherwise return "No" # Driver Code if __name__ == "__main__": S = "geeks" print(containsEqualStrings(S)) # This code is contributed by ukasp
C#
// C# program for the above approach
using System;
class GFG
{
// Function to check if any
// character is a vowel or not
public static bool isVowel(char ch)
{
// Lowercase vowels
if (ch == 'a' || ch == 'e' || ch == 'i'
|| ch == 'o' || ch == 'u')
return true;
// Uppercase vowels
if (ch == 'A' || ch == 'E' || ch == 'I'
|| ch == 'O' || ch == 'U')
return true;
// Otherwise
return false;
}
// Function to check if string S
// can be split into two substrings
// with equal number of vowels
public static String
containsEqualStrings(string S)
{
// Stores the count of vowels
// in the string S
int totalVowels = 0;
// Traverse over the string
for (int i = 0;
i < S.Length; i++)
{
// If S[i] is vowel
if (isVowel(S[i]))
totalVowels++;
}
// Stores the count of vowels
// upto the current index
int vowelsTillNow = 0;
// Traverse over the string
for (int i = 0;
i < S.Length; i++) {
// If S[i] is vowel
if (isVowel(S[i])) {
vowelsTillNow++;
totalVowels--;
// If vowelsTillNow and
// totalVowels are equal
if (vowelsTillNow
== totalVowels) {
return "Yes";
}
}
}
// Otherwise
return "No";
}
// Driver Code
static public void Main()
{
string S = "geeks";
Console.WriteLine(
containsEqualStrings(S));
}
}
// This code is contributed by code_hunt.
Javascript
<script>
// JavaScript program for the above approach
// Function to check if any
// character is a vowel or not
function isVowel(ch) {
// Lowercase vowels
if (ch === "a" || ch === "e" || ch === "i" || ch === "o" || ch === "u")
return true;
// Uppercase vowels
if (ch === "A" || ch === "E" || ch === "I" || ch === "O" || ch === "U")
return true;
// Otherwise
return false;
}
// Function to check if string S
// can be split into two substrings
// with equal number of vowels
function containsEqualStrings(S) {
// Stores the count of vowels
// in the string S
var totalVowels = 0;
// Traverse over the string
for (var i = 0; i < S.length; i++) {
// If S[i] is vowel
if (isVowel(S[i])) totalVowels++;
}
// Stores the count of vowels
// upto the current index
var vowelsTillNow = 0;
// Traverse over the string
for (var i = 0; i < S.length; i++) {
// If S[i] is vowel
if (isVowel(S[i])) {
vowelsTillNow++;
totalVowels--;
// If vowelsTillNow and
// totalVowels are equal
if (vowelsTillNow === totalVowels) {
return "Yes";
}
}
}
// Otherwise
return "No";
}
// Driver Code
var S = "geeks";
document.write(containsEqualStrings(S));
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)