1405. Longest Happy String

MediumGreedyStringHeap (Priority Queue)
Leetcode Link

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:

  1. Consists only of the letters 'a', 'b', and 'c'.
  2. Does not include the substring "aaa", "bbb", or "ccc".
  3. 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:

  1. 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.
  2. 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.
  3. 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.
  4. 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).
  5. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following problems can be solved with backtracking (select multiple)

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:

  1. 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.

  2. 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).

  3. 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.

  4. Termination:

    • The loop ends when the heap is empty or when no more characters can be added without violating the happy string condition.

  5. Result:

    • The list ans is then joined to form a string, which is the resulting longest happy string that we return.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a good use case for backtracking?

Example 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.

  1. 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.

  2. The "happy" string, ans, is initially empty. We then pop elements from the heap and check if we can add them to ans.

  3. The heap gives us (-3, 'b') first because it has the largest magnitude count. We can safely add 'b' to ans without violating any rules since ans is empty.

  4. 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').

  5. We pop the next highest count, (-2, 'b'). Since we can have two 'b's in a row, we add 'b' to ans, decrement the count to -1, and push it back. Now, ans = ['b', 'b'] and the heap is (-2, 'c'), (-1, 'b'), (-1, 'a').

  6. 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' to ans, decrement the count to -1, and push it back. Now, ans = ['b', 'b', 'c'] and the heap is (-1, 'b'), (-1, 'c'), (-1, 'a').

  7. 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').

  8. 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'].

  9. 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.

  10. We have ans = ['b', 'b', 'c', 'c', 'b', 'a'], which is our longest happy string from the given counts.

  11. 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
Not Sure What to Study? Take the 2-min Quiz：

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

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 heap h, 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 in O(log n), where n is the number of elements in the heap. However, since our heap can at most contain three elements, this simplifies to a constant time O(1).
  • Each heappush also runs in O(log n), which again simplifies to O(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 space O(1).
  • The answer list ans, which can grow up to the length of the maximum possible diverse string, which is 2 * (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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following uses divide and conquer strategy?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 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 When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Heap Fundamentals

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫