String dada str de tamaño par N que consta de alfabetos ingleses en minúsculas. La tarea es encontrar el número de strings rotadas de str que tienen más vocales en la primera mitad que en la segunda mitad.
Ejemplos:
Entrada: str = “abcd”
Salida: 2
Explicación:
Todas las strings giradas son “abcd”, “dabc”, “cdab”, “bcda”.
Las dos primeras strings giradas tienen más vocales en
la primera mitad que en la segunda mitad.Entrada: str = “abecidft”
Salida: 4
Explicación:
Hay 4 strings posibles con rotación donde hay más vocales en la primera mitad que en la segunda mitad.
Enfoque: un enfoque eficiente es hacer que la string s = str + str luego el tamaño de s sea 2 * N . Ahora, crea una array de prefijos para almacenar el número de vocales presentes desde el índice 0 hasta el índice i. Luego ejecute un ciclo de N – 1 a 2 * N – 2 para obtener todas las strings rotadas de str . Encuentre el recuento de strings rotadas requeridas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of rotated
// strings which have more number of vowels in
// the first half than the second half
int cntRotations(string s, int n)
{
// Create a new string
string str = s + s;
// Pre array to store count of all vowels
int pre[2 * n] = { 0 };
// Compute the prefix array
for (int i = 0; i < 2 * n; i++) {
if (i != 0)
pre[i] += pre[i - 1];
if (str[i] == 'a' || str[i] == 'e'
|| str[i] == 'i' || str[i] == 'o'
|| str[i] == 'u') {
pre[i]++;
}
}
// To store the required answer
int ans = 0;
// Find all rotated strings
for (int i = n - 1; i < 2 * n - 1; i++) {
// Right and left index of the string
int r = i, l = i - n;
// x1 stores the number of vowels
// in the rotated string
int x1 = pre[r];
if (l >= 0)
x1 -= pre[l];
r = i - n / 2;
// Left stores the number of vowels
// in the first half of rotated string
int left = pre[r];
if (l >= 0)
left -= pre[l];
// Right stores the number of vowels
// in the second half of rotated string
int right = x1 - left;
// If the count of vowels in the first half
// is greater than the count in the second half
if (left > right) {
ans++;
}
}
// Return the required answer
return ans;
}
// Driver code
int main()
{
string s = "abecidft";
int n = s.length();
cout << cntRotations(s, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the count of rotated
// Strings which have more number of vowels in
// the first half than the second half
static int cntRotations(String s, int n)
{
// Create a new String
String str = s + s;
// Pre array to store count of all vowels
int pre[]=new int[2 * n] ;
// Compute the prefix array
for (int i = 0; i < 2 * n; i++)
{
if (i != 0)
pre[i] += pre[i - 1];
if (str.charAt(i) == 'a' || str.charAt(i) == 'e' ||
str.charAt(i) == 'i' || str.charAt(i) == 'o' ||
str.charAt(i) == 'u')
{
pre[i]++;
}
}
// To store the required answer
int ans = 0;
// Find all rotated Strings
for (int i = n - 1; i < 2 * n - 1; i++)
{
// Right and left index of the String
int r = i, l = i - n;
// x1 stores the number of vowels
// in the rotated String
int x1 = pre[r];
if (l >= 0)
x1 -= pre[l];
r = i - n / 2;
// Left stores the number of vowels
// in the first half of rotated String
int left = pre[r];
if (l >= 0)
left -= pre[l];
// Right stores the number of vowels
// in the second half of rotated String
int right = x1 - left;
// If the count of vowels in the first half
// is greater than the count in the second half
if (left > right)
{
ans++;
}
}
// Return the required answer
return ans;
}
// Driver code
public static void main(String args[])
{
String s = "abecidft";
int n = s.length();
System.out.println( cntRotations(s, n));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach # Function to return the count of rotated # strings which have more number of vowels in # the first half than the second half def cntRotations(s, n): # Create a new string str = s + s; # Pre array to store count of all vowels pre = [0] * (2 * n); # Compute the prefix array for i in range(2 * n): if (i != 0): pre[i] += pre[i - 1]; if (str[i] == 'a' or str[i] == 'e' or str[i] == 'i' or str[i] == 'o' or str[i] == 'u'): pre[i] += 1; # To store the required answer ans = 0; # Find all rotated strings for i in range(n - 1, 2 * n - 1, 1): # Right and left index of the string r = i; l = i - n; # x1 stores the number of vowels # in the rotated string x1 = pre[r]; if (l >= 0): x1 -= pre[l]; r = (int)(i - n / 2); # Left stores the number of vowels # in the first half of rotated string left = pre[r]; if (l >= 0): left -= pre[l]; # Right stores the number of vowels # in the second half of rotated string right = x1 - left; # If the count of vowels in the first half # is greater than the count in the second half if (left > right): ans += 1; # Return the required answer return ans; # Driver code s = "abecidft"; n = len(s); print(cntRotations(s, n)); # This code is contributed by Rajput-Ji
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the count of rotated
// Strings which have more number of vowels in
// the first half than the second half
static int cntRotations(string s, int n)
{
// Create a new String
string str = s + s;
// Pre array to store count of all vowels
int []pre = new int[2 * n];
// Compute the prefix array
for (int i = 0; i < 2 * n; i++)
{
if (i != 0)
pre[i] += pre[i - 1];
if (str[i] == 'a' || str[i] == 'e' ||
str[i] == 'i' || str[i] == 'o' ||
str[i] == 'u')
{
pre[i]++;
}
}
// To store the required answer
int ans = 0;
// Find all rotated Strings
for (int i = n - 1; i < 2 * n - 1; i++)
{
// Right and left index of the String
int r = i, l = i - n;
// x1 stores the number of vowels
// in the rotated String
int x1 = pre[r];
if (l >= 0)
x1 -= pre[l];
r = i - n / 2;
// Left stores the number of vowels
// in the first half of rotated String
int left = pre[r];
if (l >= 0)
left -= pre[l];
// Right stores the number of vowels
// in the second half of rotated String
int right = x1 - left;
// If the count of vowels in the first half
// is greater than the count in the second half
if (left > right)
{
ans++;
}
}
// Return the required answer
return ans;
}
// Driver code
public static void Main()
{
String s = "abecidft";
int n = s.Length;
Console.WriteLine( cntRotations(s, n));
}
}
// This code is contributed by AnkitRai01
Javascript
<script>
// Javascript implementation of the approach
// Function to return the count of rotated
// Strings which have more number of vowels in
// the first half than the second half
function cntRotations(s, n)
{
// Create a new String
let str = s + s;
// Pre array to store count of all vowels
let pre = new Array(2 * n);
pre.fill(0);
// Compute the prefix array
for (let i = 0; i < 2 * n; i++)
{
if (i != 0)
pre[i] += pre[i - 1];
if (str[i] == 'a' || str[i] == 'e' ||
str[i] == 'i' || str[i] == 'o' ||
str[i] == 'u')
{
pre[i]++;
}
}
// To store the required answer
let ans = 0;
// Find all rotated Strings
for (let i = n - 1; i < 2 * n - 1; i++)
{
// Right and left index of the String
let r = i, l = i - n;
// x1 stores the number of vowels
// in the rotated String
let x1 = pre[r];
if (l >= 0)
x1 -= pre[l];
r = i - parseInt(n / 2, 10);
// Left stores the number of vowels
// in the first half of rotated String
let left = pre[r];
if (l >= 0)
left -= pre[l];
// Right stores the number of vowels
// in the second half of rotated String
let right = x1 - left;
// If the count of vowels in the first half
// is greater than the count in the second half
if (left > right)
{
ans++;
}
}
// Return the required answer
return ans;
}
let s = "abecidft";
let n = s.length;
document.write(cntRotations(s, n));
</script>
Producción
4
Complejidad de Tiempo: O(2 * N)
Espacio Auxiliar: O(2 * N)
Enfoque eficiente: para reducir la complejidad del espacio a constante para el enfoque anterior, almacene el número de vocales en ambas mitades en dos variables e itere a través de toda la rotación cambiando el índice.
- En cada rotación, el primer elemento de la primera mitad se elimina y se inserta en la segunda mitad y, si este elemento es una vocal, se reduce el número de vocales en la primera mitad en 1 y se aumenta el número de vocales en la segunda. -la mitad por 1.
- El primer elemento de la segunda mitad se elimina y se inserta en la primera mitad y, si este elemento es una vocal, aumenta el número de vocales en la primera mitad en 1 y disminuye el número de vocales en la segunda mitad en 1. .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of
// rotated strings which have more
// number of vowels in the first
// half than the second half
int cntRotations(char s[], int n)
{
int lh = 0, rh = 0, i, ans = 0;
// Compute the number of
// vowels in first-half
for(i = 0; i < n / 2; ++i)
if (s[i] == 'a' || s[i] == 'e' ||
s[i] == 'i' || s[i] == 'o' ||
s[i] == 'u')
{
lh++;
}
// Compute the number of
// vowels in second-half
for(i = n / 2; i < n; ++i)
if (s[i] == 'a' || s[i] == 'e' ||
s[i] == 'i' || s[i] == 'o' ||
s[i] == 'u')
{
rh++;
}
// Check if first-half
// has more vowels
if (lh > rh)
ans++;
// Check for all possible rotations
for(i = 1; i < n; ++i)
{
if (s[i - 1] == 'a' || s[i - 1] == 'e' ||
s[i - 1] == 'i' || s[i - 1] == 'o' ||
s[i - 1] == 'u')
{
rh++;
lh--;
}
if (s[(i - 1 + n / 2) % n] == 'a' ||
s[(i - 1 + n / 2) % n] == 'e' ||
s[(i - 1 + n / 2) % n] == 'i' ||
s[(i - 1 + n / 2) % n] == 'o' ||
s[(i - 1 + n / 2) % n] == 'u')
{
rh--;
lh++;
}
if (lh > rh)
ans++;
}
// Return the answer
return ans;
}
// Driver code
int main()
{
char s[] = "abecidft";
int n = strlen(s);
// Function call
cout << " " << cntRotations(s, n);
return 0;
}
// This code is contributed by shivanisinghss2110
C
// C implementation of the approach
#include <stdio.h>
#include <string.h>
// Function to return the count of
// rotated strings which have more
// number of vowels in the first
// half than the second half
int cntRotations(char s[], int n)
{
int lh = 0, rh = 0, i, ans = 0;
// Compute the number of
// vowels in first-half
for (i = 0; i < n / 2; ++i)
if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i'
|| s[i] == 'o' || s[i] == 'u')
{
lh++;
}
// Compute the number of
// vowels in second-half
for (i = n / 2; i < n; ++i)
if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i'
|| s[i] == 'o' || s[i] == 'u') {
rh++;
}
// Check if first-half
// has more vowels
if (lh > rh)
ans++;
// Check for all possible rotations
for (i = 1; i < n; ++i) {
if (s[i - 1] == 'a' || s[i - 1] == 'e'
|| s[i - 1] == 'i' || s[i - 1] == 'o'
|| s[i - 1] == 'u') {
rh++;
lh--;
}
if (s[(i - 1 + n / 2) % n] == 'a'
|| s[(i - 1 + n / 2) % n] == 'e'
|| s[(i - 1 + n / 2) % n] == 'i'
|| s[(i - 1 + n / 2) % n] == 'o'
|| s[(i - 1 + n / 2) % n] == 'u') {
rh--;
lh++;
}
if (lh > rh)
ans++;
}
// Return the answer
return ans;
}
// Driver code
int main()
{
char s[] = "abecidft";
int n = strlen(s);
// Function call
printf("%d", cntRotations(s, n));
return 0;
}
Java
// Java implementation of
// the approach
class GFG{
// Function to return the count of
// rotated strings which have more
// number of vowels in the first
// half than the second half
public static int cntRotations(char s[],
int n)
{
int lh = 0, rh = 0, i, ans = 0;
// Compute the number of
// vowels in first-half
for (i = 0; i < n / 2; ++i)
if (s[i] == 'a' || s[i] == 'e' ||
s[i] == 'i' || s[i] == 'o' ||
s[i] == 'u')
{
lh++;
}
// Compute the number of
// vowels in second-half
for (i = n / 2; i < n; ++i)
if (s[i] == 'a' || s[i] == 'e' ||
s[i] == 'i' || s[i] == 'o' ||
s[i] == 'u')
{
rh++;
}
// Check if first-half
// has more vowels
if (lh > rh)
ans++;
// Check for all possible
// rotations
for (i = 1; i < n; ++i)
{
if (s[i - 1] == 'a' || s[i - 1] == 'e' ||
s[i - 1] == 'i' || s[i - 1] == 'o' ||
s[i - 1] == 'u')
{
rh++;
lh--;
}
if (s[(i - 1 + n / 2) % n] == 'a' ||
s[(i - 1 + n / 2) % n] == 'e' ||
s[(i - 1 + n / 2) % n] == 'i' ||
s[(i - 1 + n / 2) % n] == 'o' ||
s[(i - 1 + n / 2) % n] == 'u')
{
rh--;
lh++;
}
if (lh > rh)
ans++;
}
// Return the answer
return ans;
}
// Driver code
public static void main(String[] args)
{
char s[] = {'a','b','e','c',
'i','d','f','t'};
int n = s.length;
// Function call
System.out.println(
cntRotations(s, n));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 implementation of the approach # Function to return the count of # rotated strings which have more # number of vowels in the first # half than the second half def cntRotations(s, n): lh, rh, ans = 0, 0, 0 # Compute the number of # vowels in first-half for i in range (n // 2): if (s[i] == 'a' or s[i] == 'e' or s[i] == 'i' or s[i] == 'o' or s[i] == 'u'): lh += 1 # Compute the number of # vowels in second-half for i in range (n // 2, n): if (s[i] == 'a' or s[i] == 'e' or s[i] == 'i' or s[i] == 'o' or s[i] == 'u'): rh += 1 # Check if first-half # has more vowels if (lh > rh): ans += 1 # Check for all possible rotations for i in range (1, n): if (s[i - 1] == 'a' or s[i - 1] == 'e' or s[i - 1] == 'i' or s[i - 1] == 'o' or s[i - 1] == 'u'): rh += 1 lh -= 1 if (s[(i - 1 + n // 2) % n] == 'a' or s[(i - 1 + n // 2) % n] == 'e' or s[(i - 1 + n // 2) % n] == 'i' or s[(i - 1 + n // 2) % n] == 'o' or s[(i - 1 + n // 2) % n] == 'u'): rh -= 1 lh += 1 if (lh > rh): ans += 1 # Return the answer return ans # Driver code if __name__ == "__main__": s = "abecidft" n = len(s) # Function call print(cntRotations(s, n)) # This code is contributed by Chitranayal
C#
// C# implementation of
// the approach
using System;
class GFG
{
// Function to return the count of
// rotated strings which have more
// number of vowels in the first
// half than the second half
static int cntRotations(char[] s, int n)
{
int lh = 0, rh = 0, i, ans = 0;
// Compute the number of
// vowels in first-half
for (i = 0; i < n / 2; ++i)
if (s[i] == 'a' || s[i] == 'e' ||
s[i] == 'i' || s[i] == 'o' ||
s[i] == 'u')
{
lh++;
}
// Compute the number of
// vowels in second-half
for (i = n / 2; i < n; ++i)
if (s[i] == 'a' || s[i] == 'e' ||
s[i] == 'i' || s[i] == 'o' ||
s[i] == 'u')
{
rh++;
}
// Check if first-half
// has more vowels
if (lh > rh)
ans++;
// Check for all possible
// rotations
for (i = 1; i < n; ++i)
{
if (s[i - 1] == 'a' || s[i - 1] == 'e' ||
s[i - 1] == 'i' || s[i - 1] == 'o' ||
s[i - 1] == 'u')
{
rh++;
lh--;
}
if (s[(i - 1 + n / 2) % n] == 'a' ||
s[(i - 1 + n / 2) % n] == 'e' ||
s[(i - 1 + n / 2) % n] == 'i' ||
s[(i - 1 + n / 2) % n] == 'o' ||
s[(i - 1 + n / 2) % n] == 'u')
{
rh--;
lh++;
}
if (lh > rh)
ans++;
}
// Return the answer
return ans;
}
// Driver code
static void Main()
{
char[] s = {'a','b','e','c',
'i','d','f','t'};
int n = s.Length;
// Function call
Console.WriteLine(cntRotations(s, n));
}
}
// This code is contributed by divyesh072019
Javascript
<script>
// Javascript implementation of the approach
// Function to return the count of
// rotated strings which have more
// number of vowels in the first
// half than the second half
function cntRotations(s, n)
{
let lh = 0, rh = 0, i, ans = 0;
// Compute the number of
// vowels in first-half
for (i = 0; i < parseInt(n / 2, 10); ++i)
if (s[i] == 'a' || s[i] == 'e' ||
s[i] == 'i' || s[i] == 'o' ||
s[i] == 'u')
{
lh++;
}
// Compute the number of
// vowels in second-half
for (i = parseInt(n / 2, 10); i < n; ++i)
if (s[i] == 'a' || s[i] == 'e' ||
s[i] == 'i' || s[i] == 'o' ||
s[i] == 'u')
{
rh++;
}
// Check if first-half
// has more vowels
if (lh > rh)
ans++;
// Check for all possible
// rotations
for (i = 1; i < n; ++i)
{
if (s[i - 1] == 'a' || s[i - 1] == 'e' ||
s[i - 1] == 'i' || s[i - 1] == 'o' ||
s[i - 1] == 'u')
{
rh++;
lh--;
}
if (s[(i - 1 + n / 2) % n] == 'a' ||
s[(i - 1 + n / 2) % n] == 'e' ||
s[(i - 1 + n / 2) % n] == 'i' ||
s[(i - 1 + n / 2) % n] == 'o' ||
s[(i - 1 + n / 2) % n] == 'u')
{
rh--;
lh++;
}
if (lh > rh)
ans++;
}
// Return the answer
return ans;
}
// Driver code
let s = ['a','b','e','c','i','d','f','t'];
let n = s.length;
// Function call
document.write(cntRotations(s, n));
// This code is contributed by rameshtravel07.
</script>
Producción
4
Complejidad de tiempo: O(n)
Complejidad de espacio: O(1)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA