Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
173 views

image

 

image


 

 

in Online Assessments by Expert (124,340 points)
edited by | 173 views

1 Answer

0 like 0 dislike

Understanding :- Given a binary string of size “N”; reverse that string 

 

But by doing this operation :- Pick any character from the string and put it at the end. 


 

Do a minimum number of operations to achieve this. 

 

Input - 0100110

Output - 3. 

 

Observation :- Observe what all characters are put in the end to generate the reverse. 




 

Observation :- You always pick some characters and put them in the end in any order you want 

 

Let’s say “k” is the answer 

 

It means we must have picked surely k subset of characters from original string and must have put them in the back 

 

Order of fixing the k last characters doesn't matter just check what frequency of 0 and 1 you need in the last k places and extract it from the original string 

 

10011000011

->

11000011001

 

K = 2. 

 

After picking the two characters for the end; the remaining string of n-2 length should match the first n-2 characters of reversed string 

 

Time Complexity - O(N)

 

Takes O(1) size. 


 

C++ - https://ideone.com/6BPkSf

Java - https://ideone.com/MA592M

Py - https://ideone.com/4brKEG

 

by Expert (124,340 points)