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 mosta
occurrences of the letter'a'
, at mostb
occurrences of the letter'b'
and at mostc
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 = "" def canAdd(res, x): 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 if canAdd(res, char): 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(''); }