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
Solution: Greedy
Put the char with highest frequency first if its consecutive length of that char is < 2
or put one char if any of other two chars has consecutive length of 2.
increase the consecutive length of itself and reset that for other two chars.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua class Solution { public: string longestDiverseString(int a, int b, int c) { const int total = a + b + c; vector<int> f{a, b, c}; vector<int> l{0, 0, 0}; string ans; for (int _ = 0; _ < total; ++_) for (int i = 0; i < 3; ++i) { const int j = (i + 1) % 3; const int k = (i + 2) % 3; if ((f[i] >= f[j] && f[i] >= f[k] && l[i] != 2) || (f[i] > 0 && (l[j] == 2 || l[k] == 2))) { ans += 'a' + i; ++l[i]; --f[i]; l[j] = l[k] = 0; break; } } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment