We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
If the tops aren't the same, you should pick the smallest.
The key to the problem is considering what should happen if the tops are the same.
We are interested in the first character that is different from the current top.
Take for example the stacks BBBA... and BBBB... in this case you will want to consume the left stack first, so that yo u can put the A earlier in the string.
Therefore you can compare the entire string to arrive at the solution, as BBBA... < BBBB... returns True.
However, there is a special case where the entire substring fits in the other.
Consider CCC and CCC... Then CCC < CCC... will return True. However we will always want to consume the longer stack:
Consider CCC, CCCA. -> Then CCCACCC is better than CCCCCCCA.
Consider CCC, CCCD. -> Consuming CCC gives us option to start consuming CCC or D. End up optimal with CCCCCCD.
To fix this you can append any character c that has [A-Z] < c. Then CCCa < CCC...a will return False and instruct us to go for the longest stack
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Morgan and a String
You are viewing a single comment's thread. Return to all comments →
If the tops aren't the same, you should pick the smallest.
The key to the problem is considering what should happen if the tops are the same. We are interested in the first character that is different from the current top. Take for example the stacks BBBA... and BBBB... in this case you will want to consume the left stack first, so that yo u can put the A earlier in the string. Therefore you can compare the entire string to arrive at the solution, as BBBA... < BBBB... returns True. However, there is a special case where the entire substring fits in the other. Consider CCC and CCC... Then CCC < CCC... will return True. However we will always want to consume the longer stack: Consider CCC, CCCA. -> Then CCCACCC is better than CCCCCCCA. Consider CCC, CCCD. -> Consuming CCC gives us option to start consuming CCC or D. End up optimal with CCCCCCD.
To fix this you can append any character c that has [A-Z] < c. Then CCCa < CCC...a will return False and instruct us to go for the longest stack