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 .
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.
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,
If there is a vowel in the last position of the first part,
It comes to the second part, so we update accordingly.
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.
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].
.
