String Rotation Problem

help
3

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

1 Like
4

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

5

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
6

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

1 Like
7

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
8

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
9

how many times we have to iterate

1 Like
10

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

2 Likes
11

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
12

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

2 Likes
13

Here u go 5TFGyZ - Online C++0x Compiler & Debugging Tool - Ideone.com
If u think any test case output give WA , tell me :slight_smile:

1 Like
14

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
15

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

16

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

17

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 5TFGyZ - Online C++0x Compiler & Debugging Tool - Ideone.com please see this.

1 Like
18

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

1 Like
19

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

20

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

21
22

Closed on user’s request.