0 like 0 dislike
174 views

edited | 174 views

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.

by Expert (124,340 points)