rr459595's blog

Weekly Leetcode contest 183 problem. Greedy solution Proof
By rr459595, history, 4 years ago, In English

Although I understand the intuition behind the solution, I am not able to prove the greedy approach formally. Can someone please help me with the proof of greedy solution for this problem ( https://leetcode.com/problems/longest-happy-string/ ) ?

Thanks.

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it
  • Let's say we are building the string, Without the loss of generality let's assume, a is the character with the highest frequency available. So according to the greedy approach, we are appending a to the string and finally, the length we got is $$$K$$$.
  • Let's assume this greedy solution is wrong and we can build a string with length $$$K + 1$$$ by appending b. So, that string will be of the form b....a..... We can take that a out of the string and put it in front of it and make a string like ab..... which is a string starting from a and have length $$$K + 1$$$. So our assumption is wrong and the greedy approach is right.

Update — Adding from my own comment below, why we can always find such occurrence of a without violating any of the conditions.

We can always find some occurrence of a which will not have something like xxax (which can violate the condition of not having three consecutive equal characters). To have that situation for all occurrences of character a, we would need to have something like xxaxxaxxaxxax. If there are M occurrences of a, then we will need at least $$$2 * M + 1$$$ occurrences of other characters (that is b and c combined). But as a is the character with $$$highest$$$ frequency that is not possible (we can atmax have $$$2 * M$$$ occurrences of other characters combined). Hence we can always find such occurrence of a which we can take out and put in front of the string.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Sorry, I am not able to get you. I was asking about the proof of the greedy approach mentioned here ( https://leetcode.com/problems/longest-happy-string/discuss/564580/Intuitive-Python-Solution-Using-Counter-with-Explantion ) .

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      You should've provided the link to that approach with your question. Anyway Let me add the greedy approach which I thought of after reading the problem (and for which the proof is).

      • Start from the empty string, find which character has the highest frequency remaining. Append this character to the string if you can (If last two characters are same as this, then you can't), otherwise append the character with second highest frequency.
      • Keep doing this step until you can, if you can't append any more characters, then that is the answer.
      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it -9 Vote: I do not like it

        During the live contest, I used a similar approach as yours and got W.A (maybe I missed something) . Have you checked it by submitting the code ?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it -7 Vote: I do not like it

          No, I don't take part in leetcode contest. But as I already provided a formal proof for this approach, it's highly likely that you did some mistake in implementation.

          → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    "We can take that a out of the string and put it in front of it"

    The problem here is when taking "a" out of the string, you may have taken it from "babb" or "ccac" and created a bad string.

    I think one possible rigorous proof might be organized as follows:

    1. The full length string will use up all of the 2nd and 3rd most frequent letters
    2. The non-greedy string can insert an extra "a" at the first character where it diverges from the greedy string.

    but again, this requires proof.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      To have that situation for all occurrences of character a, we would need to have something like xxaxxaxxaxxax. If there are $$$M$$$ occurrences of a, then we will need at least $$$2 * M + 1$$$ occurrences of other characters (that is b and c combined). But as a is the character with $$$highest$$$ frequency that is not possible (we can atmax have $$$2 * M$$$ occurrences of other characters combined). Hence we can always have find such occurrence of a which we can take out and put it in front of the string.

      → Reply