1405. Longest Happy String
Problem Description
The problem provides us with a unique challenge to construct the longest happy string possible using only the letters 'a', 'b', and 'c', under certain constraints. A happy string is one that:
- Consists only of the letters 'a', 'b', and 'c'.
- Does not include the substring "aaa", "bbb", or "ccc".
- Contains at most 'a' occurrences of 'a', 'b' occurrences of 'b', and 'c' occurrences of 'c', where 'a', 'b', and 'c' are also the given integers that represent the maximum allowed occurrences of these letters.
The task is to return the longest happy string that can be constructed according to these rules. If multiple solutions exist that have the same length, any of them would be an acceptable answer. If no such string can be created, the function should return an empty string.
Intuition
To solve this problem efficiently, we must prioritize inserting letters with the highest remaining count, while also ensuring that we don't insert more than two consecutive identical letters. Using a greedy approach will lead us to a solution that maximizes the length of the happy string.
Here's the intuition behind the solution:
- We should always try to add the letter with the maximum count to the result. However, we must also ensure that we don't exceed two consecutive occurrences.
- In order to keep track of the letters and their counts efficiently and to always get the one with the maximum count, we can use a max-heap. In Python, heapq is a min-heap, so we insert negative counts to simulate a max-heap.
- Once we pop the letter with the maximum count (using negative values for max-heap behavior), we have two scenarios:
- If this letter is the same as the last two letters of our current string, we should add the letter with the next highest count instead (if available) to prevent three consecutive identical letters.
- If it's safe to add (not forming three consecutive identical letters), we add the letter to our result.
- After adding a letter from the heap to the result string, we must decrement its count and push it back into the heap if it still has a positive count (since we are working with negative values, we increment the negative count).
- We repeat this process until the heap is empty or until we can no longer add letters without breaking the happiness condition.
This approach ensures that we are adding letters in a way that always seeks to maximize the string's length while adhering to the constraints provided by the problem.
Learn more about Greedy and Heap (Priority Queue) patterns.
Solution Approach
The solution uses a max-heap to always get the character with the highest remaining count that can be added to the "happy" string. The Python heapq
library is utilized, but since it only supports min-heaps, we insert negative counts for conversion to max-heap behavior. Here is a step-by-step walkthrough of the implementation:
-
Initialization of the Heap:
- We start by initializing an empty list
h
to serve as our heap. - For each character
'a'
,'b'
, and'c'
, if the count is greater than 0, we push tuple(-count, char)
onto the heap. The negative count ensures that the character with the highest count is at the top of the heap.
- We start by initializing an empty list
-
Construction of the Happy String:
- An empty list
ans
is created to build our happy string. - We then enter a loop that continues until the heap is empty.
- Inside the loop, we use
heappop
to remove and retrieve the character with the maximum count (while accounting for the negative sign).
- An empty list
-
Adding Characters to the String:
- We need to check whether adding this character would violate the condition of having three consecutive identical characters.
- If it does, we check if there is another character in the heap. If so, we pop the next character, append it to the
ans
list, decrement its count (by incrementing the negative value), and push it back onto the heap if the count is still positive. - If there are no more characters or we can add the top character, we append the character to
ans
, decrement the count, and push it back onto the heap if it is still above zero.
-
Termination:
- The loop ends when the heap is empty or when no more characters can be added without violating the happy string condition.
-
Result:
- The list
ans
is then joined to form a string, which is the resulting longest happy string that we return.
- The list
The usage of the heap data structure is critical for efficiently retrieving the character with the highest count. This, combined with checking the last two characters of the current string, ensures adherence to the problem constraints while maximizing the string's length. The pattern followed is a form of a greedy approach, prioritizing local optimal choices with the aim of finding a global optimum for the happy string length.
The solution is elegant and efficient as it runs in O(n log k)
time complexity where n
is the total number of letters to be placed in the string and k
is the number of unique characters (k
is 3 in this case, so practically O(n)
), and O(k)
space complexity for the heap which stores at most one entry per unique character.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example where we have the maximum number of 'a'
occurrences as 1, 'b'
occurrences as 3, and 'c'
occurrences as 2, i.e., a = 1, b = 3, c = 2
.
-
We initialize our heap with the given counts. The heap
h
contains(-1, 'a')
,(-3, 'b')
, and(-2, 'c')
, representing the counts, and it's in min-heap order due to the negative values. -
The "happy" string,
ans
, is initially empty. We then pop elements from the heap and check if we can add them toans
. -
The heap gives us
(-3, 'b')
first because it has the largest magnitude count. We can safely add 'b' toans
without violating any rules sinceans
is empty. -
After adding 'b', we decrement its count from -3 to -2 and push
(-2, 'b')
back into the heap. Now,ans = ['b']
and our heap is(-2, 'b'), (-2, 'c'), (-1, 'a')
. -
We pop the next highest count,
(-2, 'b')
. Since we can have two 'b's in a row, we add 'b' toans
, decrement the count to -1, and push it back. Now,ans = ['b', 'b']
and the heap is(-2, 'c'), (-1, 'b'), (-1, 'a')
. -
We cannot add another 'b' because that would result in "bbb". So we pop the next highest count, which is
(-2, 'c')
, and add 'c' toans
, decrement the count to -1, and push it back. Now,ans = ['b', 'b', 'c']
and the heap is(-1, 'b'), (-1, 'c'), (-1, 'a')
. -
Next, we can add 'c' again because it will not violate any conditions. We add 'c' to
ans
, remove it from the heap (since its count becomes 0), and continue. Now,ans = ['b', 'b', 'c', 'c']
and the heap is(-1, 'b'), (-1, 'a')
. -
Now we can add 'b' again, as it will not break the rule of three identical consecutive characters. We add 'b' to
ans
and remove it from the heap (count is now 0). Now,ans = ['b', 'b', 'c', 'c', 'b']
. -
Finally, we add 'a', since it is the only character left in the heap. We add 'a' to
ans
and the heap is now empty. -
We have
ans = ['b', 'b', 'c', 'c', 'b', 'a']
, which is our longest happy string from the given counts. -
We join the list
ans
to form the string "bbccba", which is the resulting longest happy string that we return.
This approach ensured that we added characters with the highest counts possible while avoiding three consecutive identical characters, resulting in the longest happy string achievable with the given conditions.
Solution Implementation
1from heapq import heappush, heappop
2
3class Solution:
4 def longestDiverseString(self, a: int, b: int, c: int) -> str:
5 # Initialize a max-heap to store the frequency and characters.
6 # Use negative frequency for max heap since Python has min-heap implementation by default
7 max_heap = []
8
9 # Add frequencies and characters to heap if they are greater than zero
10 if a > 0:
11 heappush(max_heap, [-a, 'a'])
12 if b > 0:
13 heappush(max_heap, [-b, 'b'])
14 if c > 0:
15 heappush(max_heap, [-c, 'c'])
16
17 # Initialize a list to construct the answer
18 result = []
19
20 # Continue until the heap is empty
21 while max_heap:
22 current_char = heappop(max_heap)
23
24 # Check if the last two characters in the result are the same as the current one
25 if len(result) >= 2 and result[-1] == current_char[1] and result[-2] == current_char[1]:
26 # If there are no other characters, break the loop to avoid having three consecutive characters
27 if not max_heap:
28 break
29
30 # Get the next character from the heap
31 next_char = heappop(max_heap)
32
33 # Add the next character to the result and decrease its frequency
34 result.append(next_char[1])
35 if -next_char[0] > 1:
36 next_char[0] += 1
37 heappush(max_heap, next_char)
38
39 # Push the current character back onto the heap for future processing
40 heappush(max_heap, current_char)
41 else:
42 # Add the current character to the result and decrease its frequency
43 result.append(current_char[1])
44 if -current_char[0] > 1:
45 current_char[0] += 1
46 heappush(max_heap, current_char)
47
48 # Join the list of characters to form the final string and return it
49 return ''.join(result)
50
51# If you need to use this class and method, you would typically create an instance of the class:
52# solution = Solution()
53# and then call the method with a, b, c values like so:
54# result = solution.longestDiverseString(a, b, c)
55
1class Solution {
2 public String longestDiverseString(int a, int b, int c) {
3 // Priority queue to store characters and their respective frequency
4 PriorityQueue<int[]> maxHeap = new PriorityQueue<>((x, y) -> y[1] - x[1]);
5
6 // Add 'a', 'b', and 'c' to the priority queue with their frequencies if they are greater than 0
7 if (a > 0) {
8 maxHeap.offer(new int[] {'a', a});
9 }
10 if (b > 0) {
11 maxHeap.offer(new int[] {'b', b});
12 }
13 if (c > 0) {
14 maxHeap.offer(new int[] {'c', c});
15 }
16
17 // StringBuilder to build the result string
18 StringBuilder result = new StringBuilder();
19
20 // Construct the string by adding characters from the priority queue
21 while (!maxHeap.isEmpty()) {
22 // Poll the character with the highest frequency
23 int[] current = maxHeap.poll();
24 int length = result.length();
25 // Check if the last two characters are the same as the current character
26 if (length >= 2 && result.charAt(length - 1) == current[0] && result.charAt(length - 2) == current[0]) {
27 // If the priority queue is empty, we can't add more characters and need to break the loop
28 if (maxHeap.isEmpty()) {
29 break;
30 }
31 // Otherwise, poll the next character to avoid three consecutive characters being the same
32 int[] next = maxHeap.poll();
33 result.append((char) next[0]);
34 // If there's more than one of the next character, decrement the count and offer it back to the queue
35 if (next[1] > 1) {
36 next[1]--;
37 maxHeap.offer(next);
38 }
39 // Offer the current character back to the queue for future consideration
40 maxHeap.offer(current);
41 } else {
42 // If there is no problem with three consecutive characters, append the current character
43 result.append((char) current[0]);
44 // Decrement the count and offer it back to the queue if there's more left
45 if (current[1] > 1) {
46 current[1]--;
47 maxHeap.offer(current);
48 }
49 }
50 }
51
52 // Convert the StringBuilder to String and return the result
53 return result.toString();
54 }
55}
56
1#include <queue>
2#include <string>
3#include <vector>
4
5using namespace std;
6
7class Solution {
8public:
9 // Generate the longest string with at most two consecutive instances of the same character when given counts of 'a', 'b', and 'c'
10 string longestDiverseString(int a, int b, int c) {
11 // Define a pair of character and int to store the character and its remaining count
12 using CharIntPair = pair<char, int>;
13
14 // Define a custom comparator for the max priority queue that will sort by the second value of the pair in descending order
15 auto compare = [](const CharIntPair& x, const CharIntPair& y) { return x.second < y.second; };
16
17 // Create a max priority queue to store the characters and their counts
18 priority_queue<CharIntPair, vector<CharIntPair>, decltype(compare)> maxHeap(compare);
19
20 // Add characters to the priority queue if their counts are greater than zero
21 if (a > 0) maxHeap.push({'a', a});
22 if (b > 0) maxHeap.push({'b', b});
23 if (c > 0) maxHeap.push({'c', c});
24
25 string result;
26
27 // Generate the string by using the top element of the priority queue as long as it's not empty
28 while (!maxHeap.empty()) {
29 CharIntPair current = maxHeap.top();
30 maxHeap.pop();
31
32 int length = result.size();
33 // Check if the last two characters of the result are the same as the current character
34 if (length >= 2 && result[length - 1] == current.first && result[length - 2] == current.first) {
35 if (maxHeap.empty()) {
36 // If there are no alternative characters, stop the process as no more characters should be consecutive
37 break;
38 }
39
40 // Use the next character in the priority queue since the current character cannot be used due to the consecutive limit
41 CharIntPair next = maxHeap.top();
42 maxHeap.pop();
43 result.push_back(next.first);
44
45 // Decrease the count of the used character and add it back to the queue if it's still greater than zero
46 if (--next.second > 0) {
47 maxHeap.push(next);
48 }
49
50 // Re-add the current character back to the queue without decrementing its count since it wasn't used
51 maxHeap.push(current);
52 } else {
53 // Add the current character to the result as it’s not forming a triplet and decrement its count
54 result.push_back(current.first);
55 if (--current.second > 0) {
56 // Only re-add it to the queue if there are more instances of that character available
57 maxHeap.push(current);
58 }
59 }
60 }
61
62 // Return the generated string which is the longest possible string without three consecutive characters being the same
63 return result;
64 }
65};
66
1function longestDiverseString(a: number, b: number, c: number): string {
2 // Initialize an array to store the result.
3 let result = [];
4 // Define an array to store the character counts using a tuple of character and its count.
5 let charStore: Array<[string, number]> = [
6 ['a', a],
7 ['b', b],
8 ['c', c],
9 ];
10
11 // Continuously loop to build the string.
12 while (true) {
13 // Sort the store array in descending order of count to always start with the character that has the most remaining.
14 charStore.sort((first, second) => second[1] - first[1]);
15
16 // Flag to determine if a next character is valid and can be added to the string.
17 let hasNextCharacter = false;
18
19 // Loop through the sorted characters to find which one can be used next.
20 for (let [index, [char, count]] of charStore.entries()) {
21 if (count === 0) {
22 // If the count for the current character is zero, skip to the next one.
23 break;
24 }
25
26 const currentLength = result.length;
27 if (currentLength >= 2 && result[currentLength - 1] === char && result[currentLength - 2] === char) {
28 // If using this character would lead to three consecutive occurrences, skip it.
29 continue;
30 }
31
32 // If the character can be used, set the flag to true and add it to the result array.
33 hasNextCharacter = true;
34 result.push(char);
35 // Decrement the count of the used character.
36 charStore[index][1] -= 1;
37
38 // Stop looking for characters since we've successfully added one.
39 break;
40 }
41
42 // If no character was valid to add, we're done building the string.
43 if (!hasNextCharacter) {
44 break;
45 }
46 }
47
48 // Join the characters in the result array to form the final string and return it.
49 return result.join('');
50}
51
Time and Space Complexity
Time Complexity
The time complexity of the code is determined by the while loop and operations such as heappush
and heappop
.
- The
while
loop runs until there are no more elements in the heaph
, which contains at most three elements (for characters 'a', 'b', 'c') and is executed every time an element is popped from the heap. - Each
heappop
operation runs inO(log n)
, wheren
is the number of elements in the heap. However, since our heap can at most contain three elements, this simplifies to a constant timeO(1)
. - Each
heappush
also runs inO(log n)
, which again simplifies toO(1)
because the heap size is limited to three. - Inside the loop, the number of operations is constant, as it involves simple condition checks and elementary arithmetic operations.
The length of the resultant string is at most 2 * (a + b + c)
(since the worst case is appending 2 of the same character for each character type before needing to add a different character). So the while loop can run for O(a + b + c)
in the case where elements are added back to the heap after every pop.
Considering the above points, the time complexity of this algorithm is therefore O(a + b + c)
.
Space Complexity
The space complexity of the code is driven by:
- The heap
h
, which at most contains three elements, thus giving us a constant spaceO(1)
. - The answer list
ans
, which can grow up to the length of the maximum possible diverse string, which is2 * (a + b + c)
.
Therefore, the space complexity is dependent on the size of the output and can be described as O(a + b + c)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.