Amazon (2024/2025) | OA | SDE| CTC- 45lpa | Coding Questions | 2024 | Set-179

Question

 

 

 

Answer 1

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