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
// OJ: https://leetcode.com/problems/longest-happy-string/
// Author: github.com/lzl124631x
// 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;
}
};