 # Find minimum no of operation to convert a string consisting of L and D all into L character

#1

Consider a string separated by spaces with L and D

so it can be

L D D L

D D D D D D L

the task is to make it all L so no D should be there and the operation you can do is Flip the character if it is D you can do L and vice versa but on fliping a character all the character on the right of it also will get flipped.
so you have to find how many minium no of operation you can do to convert it into a string of all L

exmaple

D D D D L L
2 operation
1 on index 0

L L L L D D

then on index 4

L L L L L L

.

#2

Algo:
Scan from left to right. At any position if we make a flip, it will flip all the character right to it.Now say we have made k flips already and we are at ith Position(scanning from left to right).
**We are not making any modification in input string during flip.
Now ith character can be either D or L in input string. As We have made k flips already, if k is even, D will remain D and L will remain L. If k is odd, that means this character has already seen odd number of flips. That mean D would have become L and L would have become D(You can try String in question with your hand).
Now we want to make it L in final String. There are 4 possible combination

1. k is even and ith character is L then we don’t need flip.
2. k is even and ith character is D then it needs a flip so increase the value of k by 1.
3. k is odd and ith character is L then also it need flip as it would have become D after odd number of flips. So increase k by 1.
4. k is odd and ith character is D then it doesn’t need flip because after odd flips D would have already become L.
Now move to next position(i+1 th).

code:
int minFlipNeeded(char A[], int length)
{
int k = 0; /* no of flips */
for(int i = 0; i < length; ++i)
{
if((!isOdd(k) && A[i] == ‘D’) || (isOdd(k) && A[i] == ‘L’))
{
++k;
}
}
}

``````bool isOdd(int n)
{
return (n & 1);
}``````

#3

I solved it by a different take though algorithm is same, now the only operation allowed is you can just flip the character, so start scanning the string from left to right, the moment you encounter the first D, you have to flip it, because there’s no other way of converting that D at position i to L, because if you flip one of the L before that first D, it will make L into D and to convert that D into L you have to flip again, which is equal to the string initially, so proof of correctness of this algorithm follows that you have to flip the Ds, and have not to flip L, so start scanning from left to right flip the first character you find which is D, now don’t do anything for the characters which have become L, how do you check it?? (just same odd flips then L has become D and vice versa), so the next character u get D flip that too and continue like this…