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.

`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$$$.`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.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 ) .

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).

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 ?

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.

"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:

but again, this requires proof.

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.