##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1405.html

# 1405. Longest Happy String (Medium)

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

Related Topics:
Dynamic Programming, Greedy

## Solution 1.

• class Solution {
public String longestDiverseString(int a, int b, int c) {
PriorityQueue<LetterCount> priorityQueue = new PriorityQueue<LetterCount>();
if (a > 0)
priorityQueue.offer(new LetterCount('a', a));
if (b > 0)
priorityQueue.offer(new LetterCount('b', b));
if (c > 0)
priorityQueue.offer(new LetterCount('c', c));
StringBuffer sb = new StringBuffer();
char prevLetter = 'z';
int prevCount = 0;
while (!priorityQueue.isEmpty()) {
LetterCount letterCount = priorityQueue.poll();
char letter = letterCount.letter;
int count = letterCount.count;
if (letter == prevLetter) {
if (prevCount < 2) {
int curCount = Math.min(count, 2 - prevCount);
for (int i = 0; i < curCount; i++)
sb.append(letter);
prevCount += curCount;
letterCount.count -= curCount;
if (letterCount.count > 0)
priorityQueue.offer(letterCount);
} else {
if (priorityQueue.isEmpty())
break;
LetterCount letterCount2 = priorityQueue.poll();
sb.append(letterCount2.letter);
letterCount2.count--;
if (letterCount2.count > 0)
priorityQueue.offer(letterCount2);
priorityQueue.offer(letterCount);
prevLetter = letterCount2.letter;
prevCount = 1;
}
} else {
int curCount = Math.min(count, 2);
for (int i = 0; i < curCount; i++)
sb.append(letter);
letterCount.count -= curCount;
if (letterCount.count > 0)
priorityQueue.offer(letterCount);
prevLetter = letter;
prevCount = curCount;
}
}
return sb.toString();
}
}

class LetterCount implements Comparable<LetterCount> {
char letter;
int count;

public LetterCount(char letter, int count) {
this.letter = letter;
this.count = count;
}

public int compareTo(LetterCount letterCount2) {
if (this.count != letterCount2.count)
return letterCount2.count - this.count;
else
return this.letter - letterCount2.letter;
}
}

############

class Solution {
public String longestDiverseString(int a, int b, int c) {
Queue<int[]> pq = new PriorityQueue<>((x, y) -> y[1] - x[1]);
if (a > 0) {
pq.offer(new int[] {'a', a});
}
if (b > 0) {
pq.offer(new int[] {'b', b});
}
if (c > 0) {
pq.offer(new int[] {'c', c});
}

StringBuilder sb = new StringBuilder();
while (pq.size() > 0) {
int[] cur = pq.poll();
int n = sb.length();
if (n >= 2 && sb.codePointAt(n - 1) == cur[0] && sb.codePointAt(n - 2) == cur[0]) {
if (pq.size() == 0) {
break;
}
int[] next = pq.poll();
sb.append((char) next[0]);
if (next[1] > 1) {
next[1]--;
pq.offer(next);
}
pq.offer(cur);
} else {
sb.append((char) cur[0]);
if (cur[1] > 1) {
cur[1]--;
pq.offer(cur);
}
}
}

return sb.toString();
}
}


• // OJ: https://leetcode.com/problems/longest-happy-string/
// Time: O(A+B+C)
// Space: O(1)
class Solution {
public:
string longestDiverseString(int a, int b, int c) {
int cnt[3] = {a, b, c}, prev = -1;
string ans;
while (true) {
int maxIndex = -1;
for (int i = 0; i < 3; ++i) {
if (i != prev && (maxIndex == -1 || cnt[i] > cnt[maxIndex])) maxIndex = i;
}
if (cnt[maxIndex] == 0) break;
int num = min(2, cnt[maxIndex]);
if (prev != -1 && cnt[prev] > cnt[maxIndex]) num = 1;
cnt[maxIndex] -= num;
while (num--) ans.push_back(maxIndex + 'a');
prev = maxIndex;
}
return ans;
}
};

• class Solution:
def longestDiverseString(self, a: int, b: int, c: int) -> str:
h = []
if a > 0:
heappush(h, [-a, 'a'])
if b > 0:
heappush(h, [-b, 'b'])
if c > 0:
heappush(h, [-c, 'c'])

ans = []
while len(h) > 0:
cur = heappop(h)
if len(ans) >= 2 and ans[-1] == cur[1] and ans[-2] == cur[1]:
if len(h) == 0:
break
nxt = heappop(h)
ans.append(nxt[1])
if -nxt[0] > 1:
nxt[0] += 1
heappush(h, nxt)
heappush(h, cur)
else:
ans.append(cur[1])
if -cur[0] > 1:
cur[0] += 1
heappush(h, cur)

return ''.join(ans)

############

class Solution:
def longestDiverseString(self, a: int, b: int, c: int) -> str:
d = [[a, "a"], [b, "b"], [c, "c"]]
total = a + b + c
res = ""
return len(res) < 2 or res[-1] != x or res[-2] != x
while total > 0:
d.sort(reverse=True)
for i, (count, char) in enumerate(d):
if count == 0: continue
res += char
d[i][0] -= 1
total -= 1
break
else:
break
return res

• type pair struct {
c   byte
num int
}

type hp []pair

func (a hp) Len() int            { return len(a) }
func (a hp) Swap(i, j int)       { a[i], a[j] = a[j], a[i] }
func (a hp) Less(i, j int) bool  { return a[i].num > a[j].num }
func (a *hp) Push(x interface{}) { *a = append(*a, x.(pair)) }
func (a *hp) Pop() interface{}   { l := len(*a); t := (*a)[l-1]; *a = (*a)[:l-1]; return t }

func longestDiverseString(a int, b int, c int) string {
var h hp
if a > 0 {
heap.Push(&h, pair{'a', a})
}
if b > 0 {
heap.Push(&h, pair{'b', b})
}
if c > 0 {
heap.Push(&h, pair{'c', c})
}

var ans []byte
for len(h) > 0 {
cur := heap.Pop(&h).(pair)
if len(ans) >= 2 && ans[len(ans)-1] == cur.c && ans[len(ans)-2] == cur.c {
if len(h) == 0 {
break
}
next := heap.Pop(&h).(pair)
ans = append(ans, next.c)
if next.num > 1 {
next.num--
heap.Push(&h, next)
}
heap.Push(&h, cur)
} else {
ans = append(ans, cur.c)
if cur.num > 1 {
cur.num--
heap.Push(&h, cur)
}
}
}

return string(ans)
}


• function longestDiverseString(a: number, b: number, c: number): string {
let ans = [];
let store: Array<[string, number]> = [
['a', a],
['b', b],
['c', c],
];
while (true) {
store.sort((a, b) => b[1] - a[1]);
let hasNext = false;
for (let [i, [ch, ctn]] of store.entries()) {
if (ctn < 1) {
break;
}
const n = ans.length;
if (n >= 2 && ans[n - 1] == ch && ans[n - 2] == ch) {
continue;
}
hasNext = true;
ans.push(ch);
store[i][1] -= 1;
break;
}
if (!hasNext) {
break;
}
}
return ans.join('');
}