Given a string S of length n that contains exactly $\lceil\frac{n}{3}\rceil$ b's and $\lceil\frac{2n}{3}\rceil$ a's:

Suppose the charge is 2 for each non-overlapping occurrence of aaa, and 1 for each non-overlapping occurrence of aa. Note the occurreces of aaa cannot overlap the occurrences of aa. Also, note that the price is the max possible.

Question: What is the string of length n with the minimum price over all such strings?

  • 1
    $\begingroup$ What do you think? $\endgroup$ Commented May 9, 2016 at 15:42
  • 1
    $\begingroup$ Have you tried proving that it's the cheapest? $\endgroup$ Commented May 9, 2016 at 16:05
  • 1
    $\begingroup$ You're describing a proof that it's a local minimum, which is different from proving that it's a global minimum. In any case, please take a few hours, and then, if you still haven't solved the question, let us know where you got stuck. We're not here to do your homework. $\endgroup$ Commented May 9, 2016 at 16:16
  • 1
    $\begingroup$ I don't understand the problem statement. First you say the string is given. Then you say the goal is to find a string. In your first sentence you say the string must have a certain number of a's and b's; in your question at the end there seems to be no such restriction. The title suggests yet a different question entirely. Do you want an algorithm to do something? If so, do what, and what are the running time requirements? Please edit the question to provide a clearer problem statement, as right now it is not at all clear what task you're trying to solve. $\endgroup$
    – D.W.
    Commented May 10, 2016 at 22:55
  • 1
    $\begingroup$ Also, as Yuval says, you should spend several hours trying to solve it on your own (exhausting all the natural avenues) before asking here, regardless of whether it's homework or not... and you should show us in the question what approaches you've tried and what the best solution you've come up with so far is, so we don't repeat the work you've already done. $\endgroup$
    – D.W.
    Commented May 10, 2016 at 22:56


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.