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:
sis happy and longest possible.scontains at mostaoccurrences of the letter'a', at mostboccurrences of the letter'b'and at mostcoccurrences of the letter'c'.swill 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 <= 100a + b + c > 0
Related Topics:
Dynamic Programming, Greedy
Solution 1.
// 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 { 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; } } -
// 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