Given string str of even size N consisting of lowercase English alphabets. The task is to find the number of rotated strings of str which have more vowels in the first half than the second half.
Examples:
Input: str = “abcd”
Output: 2
Explanation:
All rotated string are “abcd”, “dabc”, “cdab”, “bcda”.
The first two rotated strings have more vowels in
the first half than the second half.Input: str = “abecidft”
Output: 4
Explanation:
There are 4 possible strings with rotation where there are more vowels in first half than in the second half.
Approach: An efficient approach is to make string s = str + str then the size of the s will be 2 * N. Now, make a prefix array to store the number of vowels present from the 0th index to the ith index. Then run a loop from N – 1 to 2 * N – 2 to get all the rotated strings of str. Find the count of required rotated strings.
Below is the implementation of the above approach:
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 halfint 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 codeint main(){ string s = "abecidft"; int n = s.length(); cout << cntRotations(s, n); return 0;} |
Java
// Java implementation of the approachclass GFG{// Function to return the count of rotated// Strings which have more number of vowels in// the first half than the second halfstatic 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 codepublic 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 halfdef 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 codes = "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> |
Output
4
Time Complexity: O(2 * N)
Auxiliary Space: O(2 * N)
Efficient Approach: To reduce the Space complexity to constant for the above approach, store the number of vowels in both halves in two variables and iterate through all rotation by changing the index.
- In each rotation, the first element of the first-half gets removed and inserted into the second-half and if this element is a vowel then decrease the number of vowels in the first-half by 1 and increase the number of vowels in the second-half by 1.
- The first element of the second-half gets removed and inserted into the first-half and if this element is a vowel then increase the number of vowels in the first-half by 1 and decrease the number of vowels in the second-half by 1.
Below is the implementation of the above approach:
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 halfint 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 codeint 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 halfint 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 codeint main(){ char s[] = "abecidft"; int n = strlen(s); // Function call printf("%d", cntRotations(s, n)); return 0;} |
Java
// Java implementation of // the approachclass GFG{ // Function to return the count of// rotated strings which have more// number of vowels in the first// half than the second halfpublic 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 codepublic 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 halfdef 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 codeif __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> |
Output
4
Time Complexity: O(n)
Space Complexity: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
