Leet Code Problem Solving in C# - Longest Happy String

Leet Code Problem Solving | Data structures and algorithm (DSA) in C#

Sanjeevi Subramani's photo
Sanjeevi Subramani

Published on Oct 13, 2021

3 min read

Subscribe to my newsletter and never miss my upcoming articles

Longest Happy String

A string is called happy if it does not have any of the strings 'aaa', 'bbb' or 'ccc' as a substring.

Given three integers a, b and c, return any string s, which satisfies following conditions:

  • s is happy and longest possible.
  • s contains at most a occurrences of the letter 'a', at most b occurrences of the letter 'b' and at most c occurrences of the letter 'c'.
  • s will only contain 'a', 'b' and 'c' letters.
  • If there is no such string s return the empty string "".

Example 1:

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

Example 2:

Input: a = 2, b = 2, c = 1
Output: "aabbc"

Example 3:

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

Constraints:

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

Answer in C#:

public class Solution
{
    public string LongestDiverseString(int a, int b, int c)
    {
        StringBuilder sb = new StringBuilder();
        bool isHappy = true;
        char? nextChar;

        while (isHappy && (a > 0 || b > 0 || c > 0))
        {
            int len = sb.Length;

            if (len >= 2)
            {
                nextChar = pickNextChar(sb[len - 1], sb[len - 2], a, b, c);
            }
            else if (len == 1)
            {
                nextChar = pickNextChar(sb[0], null, a, b, c);
            }
            else
            {
                nextChar = pickNextChar(null, null, a, b, c);
            }

            if (nextChar == null)
            {
                isHappy = false;
            }
            else
            {
                sb.Append(nextChar);
                switch (nextChar)
                {
                    case 'a':
                        a--;
                        break;
                    case 'b':
                        b--;
                        break;
                    case 'c':
                        c--;
                        break;
                }
            }
        }

        return sb.ToString();
    }

    private Char? pickNextChar(Char? last, Char? secondLast, int a, int b, int c)
    {
        if (last == null || secondLast == null || !last.Equals(secondLast))
        {
            // If we are looking for the first 2 chars of the string, or the last 2 chars are not equal,
            // then we don't need to worry about string getting unhappy and can pick any of 'a', 'b' and 'c'.
            if (a >= b && a >= c)
            {
                return 'a';
            }
            else if (b >= a && b >= c)
            {
                return 'b';
            }
            else
            {
                return 'c';
            }
        }
        else
        {
            // If the last 2 chars are equal, we need to pick from the other 2 chars to avoid string getting unhappy
            switch (last)
            {
                case 'a':
                    if (b >= c)
                    {
                        if (b > 0)
                        { return 'b'; }
                        else
                        {
                            return null;
                        }
                    }
                    else if (c > 0)
                    { return 'c'; }
                    else
                    {
                        return null;
                    }
                case 'b':
                    if (a >= c)
                    {
                        if (a > 0)
                        { return 'a'; }
                        else
                        {
                            return null;
                        }
                    }
                    else if (c > 0)
                    { return 'c'; }
                    else
                    {
                        return null;
                    }
                case 'c':
                    if (a >= b)
                    {
                        if (a > 0)
                        { return 'a'; }
                        else
                        {
                            return null;
                        }
                    }
                    else if (b > 0)
                    { return 'b'; }
                    else
                    {
                        return null;
                    }
                default:
                    return null;
            }
        }
    }
}
 
Share this