{tocify} $title={Table of Contents}
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 occurrence 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;
}
}
}
}