By greedy i mean
x1 - the string with maximum no of 1 count,
x2 - less than x1,
x3 - less than x2,
now place x1 1’s from left to right and x2 1’s from right to left and then try to minimise the overlap between x1 and x2 by x3 and if still x3 remains then place it from right to left .
Why can't i apply a greedy solution here
Well this may work with some cases, but consider this example
0001
0100
1000
here answer is 1110, but your algorithm produces 1011
okay so first we can try placing x2 just after x1 and if no spaces are left then try overlapping with right part of x1 and then try to minimize that overlapping by x3
I’ll encourage you trying this as well and see the result.
i tried to write this code but it envolved so many cases that my dp solution was 1/7th the number of lines of my greedy solution . so, i lost the hope to write complete greedy solution , but still was curious to know if in case any case was their which would fail this approach !!
Actually this is the reason we prefer DP, as if you code greedy solution then you have to take care of each case which is barely impossible.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.