In this guide, you will get 1405. Longest Happy String LeetCode Solution with the best time and space complexity. The solution to Longest Happy String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
A string s is called happy if it satisfies the following conditions:
s only contains the letters ‘a’, ‘b’, and ‘c’.
s does not contain any of “aaa”, “bbb”, or “ccc” as a substring.
s contains at most a occurrences of the letter ‘a’.
s contains at most b occurrences of the letter ‘b’.
s contains at most c occurrences of the letter ‘c’.
Given three integers a, b, and c, return the longest possible happy string. If there are multiple longest happy strings, return any of them. If there is no such string, return the empty string “”.
A substring is a contiguous sequence of characters within a string.
Example 1:
Input: a = 1, b = 1, c = 7
Output: “ccaccbcc”
Explanation: “ccbccacc” would also be a correct answer.
Example 2:
Input: a = 7, b = 1, c = 0
Output: “aabaa”
Explanation: It is the only correct answer in this case.
Constraints:
0 <= a, b, c 0
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
1405. Longest Happy String LeetCode Solution in C++
class Solution {
public:
string longestDiverseString(int a, int b, int c, char A = 'a', char B = 'b',
char C = 'c') {
if (a < b)
return longestDiverseString(b, a, c, B, A, C);
if (b < c)
return longestDiverseString(a, c, b, A, C, B);
if (b == 0)
return string(min(a, 2), A);
const int useA = min(a, 2);
const int useB = (a - useA >= b) ? 1 : 0;
return string(useA, A) + string(useB, B) +
longestDiverseString(a - useA, b - useB, c, A, B, C);
}
}; /* code provided by PROGIEZ */
1405. Longest Happy String LeetCode Solution in Java
N/A // code provided by PROGIEZ
1405. Longest Happy String LeetCode Solution in Python
