String Rotation Problem

Given an even length string.

Find the no of rotations of that string that contains more vowels on left half than right half

Sample input
abcd

Sample output
2

Explanation
All rotations of abcd are
abcd,dabc,cdab,bcda

Rotations 1 and 2 contain more vowels in first half than second half So answer is 2

Pls share approaches

This problem was askes in Hashedin Coding round which I could not solve…Pls share ur approaches to solve this problem

@guitarlover @anon55659401 @taran_1407 @ssrivastava990 pls help

1 Like

Calculate the state of current string by dividing it into 2 parts.

Say the state is :-

[ 5,4 ].
Store indices of all the vowels.

Now, we calculate the answer of each rotation in O(1).

For each rotation, have a check on the last indices of vowels of first part and second part…

Just keep increasing them until they cross the limit, as soon as they cross the limit, you update your state , and you update the status/position of last index of vowel for each half part.

Take care of corner cases as well and you are done .

3 Likes

Not able to understood how you are dividing the state can u give example

1 Like

Not able to understood how you are dividing the state can u give example

We divide the string from the middle. The left state is the left part of the string, while the right one is the right part.

For eg:

abcd
We divide it into 2 states such as:
1st state: ab
2nd state: cd

2 Likes

@aryan12 @anon55659401
can u explain the above approach through example

1 Like

Count total number of vowels let this be m
Take a window half the size of the string using two pointers keep sliding this window circularly and count number of windows with number of vowels greater than m/2.

2 Likes

So basically,

Taking your example string : abcd
(Pls note I am taking 1 indexed)

First Step

We traverse through the string and see where are the vowels.
We store the indices of the vowels. Here, its [1]. We partition the string from the middle.
Thus first half is: ab
Second half is: cd

Second Step

Now store the last position of the two parts in two variables.
In each move,

  1. If there is a vowel in the last position of the first part,
    It comes to the second part, so we update accordingly.
  2. And if there is a vowel in the last position of the second part
    It comes to the first part, and we update it accordingly
Third Step

For every iteration, if the vowels in the first part is greater than the vowels in the second part, we update the answer.

Hope this helps :slight_smile:.

2 Likes

how many times we have to iterate

1 Like

Total number of rotations a string can have is equal to its length. So for "abcd" iterate 4 times.

2 Likes

If the length of the string is N, we iterate N times (considering the calculation on the default state as well). :slightly_smiling_face:

2 Likes

If u want i made a very simple code .
Btw @aryan12 u and me think exactly same :slight_smile: LOL

2 Likes

Here u go https://ideone.com/5TFGyZ
If u think any test case output give WA , tell me :slight_smile:

1 Like

Concatenate the same string once more. i.e. for example the string abcdabcd. Now observe the substrings of length L(length of original string) are actually the strings resulting after each rotation. (abcd, bcda, cdab, dabc).
Now take prefix sums for vowels pf[i] in the concatenated string.
For each i from 0 to L - 1, find if pf[i + L / 2] - pf[i - 1] > pf[i + L] - pf[i + L / 2].

3 Likes

pf[i-1] is pf[-1] if i is zero ?

That depends on implementation anyone can handle that, I just sketched the idea.

one thing @aman_robotics if we make prefix sum for vowel for concatenate string , it may gives memory error if | S | <= 10^5 …
and can i do in this way https://ideone.com/5TFGyZ please see this.

1 Like

The size for pf[ ] array would be 2 * |S|, which I don’t think should MLE.

1 Like

oh ya … my fault i thought 10^10 … LOL… SRY

for those who are thinking of an approach to this problem, must try submitting their code here.
This approach of mine makes use of 2-pointer technique