Count number of rotated strings which have more number of vowels in the first half than second half

0 0 15 minutes read

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

Output

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

Output

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