[LeetCode] Longest Happy String

Problem: A string s is called happy if it satisfies the following conditions:

• s only contains the letters 'a', 'b', and 'c'.
• s does not contain any of "aaa", "bbb", or "ccc" as a substring.
• s contains at most a occurrences of the letter 'a'.
• s contains at most b occurrences of the letter 'b'.
• s contains at most c occurrences of the letter 'c'.

Given three integers a, b, and c, return the longest possible happy string. If there are multiple longest happy strings, return any of them. If there is no such string, return the empty string "".

A substring is a contiguous sequence of characters within a string.

Example:

Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.

Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It is the only correct answer in this case.

Constraints:

• 0 <= a, b, c <= 100
• a + b + c > 0

Approach: I am using a simple greedy approach. The intuition is simple; let's say we want to put 'a' in the result "s". We can only do that in case of the number of a's remaining are more than number of 'b' and 'c' and we haven't put 'a' 2 times continuously already in the "s". The other condition could be if 'b' or 'c' are already put continuously 2 times.

The same condition can be applied for when we try to put 'b' or 'c'. That's all about the approach. Look at the implementation for more understanding.

Implementation in C#:

    public string LongestDiverseString(int a, int b, int c) 

    {

        StringBuilder sb = new StringBuilder();

        int total = a + b + c;

        int currACount = 0, currBCount = 0, currCCount = 0;

        while(total > 0)

        {

            if ((a >= b && a >= c && currACount < 2) || 

                (a > 0 && (currBCount == 2 || currCCount == 2)))

            {

                sb.Append('a');

                --a;

                currBCount = 0;

                currCCount = 0;

                ++currACount;

            }

            

            else if ((b >= a && b >= c && currBCount < 2) || 

                     (b > 0 && (currACount == 2 || currCCount == 2)))

            {

                sb.Append('b');

                --b;

                currACount = 0;

                currCCount = 0;

                ++currBCount;

            }

            else if ((c >= a && c >= b && currCCount < 2) || 

                     (c > 0 && (currACount == 2 || currBCount == 2)))

            {

                sb.Append('c');

                --c;

                currACount = 0;

                currBCount = 0;

                ++currCCount;

            }

            --total;

        }

        return sb.ToString();

    }

Complexity: O(n) where n = a + b + c