Problem
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 mosta
occurrences of the letter'a'
.s
contains at mostb
occurrences of the letter'b'
.s
contains at mostc
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.
Examples
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.
Solution
Method 1 - Greedy with MaxHeap
We should be greedy in using the char that occur most number of time. For eg. in eg1, we use c
first, in eg.2 we use a
first.
To construct the longest possible happy string while adhering to the given conditions, we need to ensure that we balance the use of ‘a’, ‘b’, and ‘c’ without letting any of them repeat more than twice consecutively. The strategy involves:
- Using a Max-Heap:
- We can use a max-heap (priority queue) to always pick the letter with the highest remaining count, while ensuring that it does not form a prohibited substring (i.e., more than two consecutive appearances).
- Heap Operations:
- Always try to append the character with the highest remaining count to the result.
- If the top character from the heap cannot be chosen (would form “aaa”, “bbb”, or “ccc”), select the next highest character that can be safely appended.
- Balancing Counts:
- After appending a character to the result, decrease its count and reinsert it into the heap (if still available).
Video explanation
Here is the video explaining this method in detail. Please check it out:
Code
Java
class Solution {
// Helper class to store character and its count
static class Pair {
char ch;
int count;
public Pair(Character ch, int count) {
this.ch = ch;
this.count = count;
}
}
public String longestDiverseString(int a, int b, int c) {
// Priority queue (max-heap) to store characters with their counts
PriorityQueue<Pair> maxHeap = new PriorityQueue<>((x, y) -> Integer.compare(y.count, x.count));
// Add all characters to the max-heap with their initial counts
if (a > 0) {
maxHeap.add(new Pair('a', a));
}
if (b > 0) {
maxHeap.add(new Pair('b', b));
}
if (c > 0) {
maxHeap.add(new Pair('c', c));
}
// StringBuilder to build the resulting happy string
StringBuilder res = new StringBuilder();
// Process characters from the max-heap to construct the string
while (!maxHeap.isEmpty()) {
// Pop the most frequent character
Pair first = maxHeap.poll();
// Check if adding this character would result in three consecutive identical characters
int resLen = res.length();
if (resLen >= 2 && res.charAt(resLen - 1) == first.ch && res.charAt(resLen - 2) == first.ch) {
// If yes, we need to use the next most frequent character if available
// No other character is available,
if (maxHeap.isEmpty()) {
break;
}
// Get the next available character
Pair second = maxHeap.poll();
// Append the most frequent character to the result and reduce its availability count
res.append(second.ch);
second.count--;
// If the next most frequent character still has counts left, push it back into the heap
if (second.count > 0) {
maxHeap.offer(second);
}
// Push the initially selected character back into the heap for later use
maxHeap.offer(first);
} else {
// Append the most frequent character to the result and reduce its availability count
res.append(first.ch);
first.count--;
// If the character still has counts left, push it back into the heap
if (first.count > 0) {
maxHeap.offer(first);
}
}
}
return res.toString();
}
}
Python
class Solution:
def longestDiverseString(self, a: int, b: int, c: int) -> str:
max_heap = []
if a > 0:
heapq.heappush(max_heap, (-a, 'a'))
if b > 0:
heapq.heappush(max_heap, (-b, 'b'))
if c > 0:
heapq.heappush(max_heap, (-c, 'c'))
res = []
while max_heap:
first = heapq.heappop(max_heap)
if len(res) >= 2 and res[-1] == res[-2] == first[1]:
if not max_heap:
break
second = heapq.heappop(max_heap)
res.append(second[1])
if second[0] + 1 < 0:
heapq.heappush(max_heap, (second[0] + 1, second[1]))
heapq.heappush(max_heap, first)
else:
res.append(first[1])
if first[0] + 1 < 0:
heapq.heappush(max_heap, (first[0] + 1, first[1]))
return "".join(res)
Complexity
- ⏰ Time complexity:
O((a + b + c) log 3)
as each insertion and extraction from the heap takesO(log 3)
, and we’re processing all letters (a + b + c
operations). - 🧺 Space complexity:
O(1)
additional space since we’re only using a few variables and the heap’s maximum size is fixed.