Leetcode 1405: Longest Happy String
You are given three integers, a, b, and c, representing the maximum occurrences of ‘a’, ‘b’, and ‘c’ that can appear in a string. Your task is to return the longest string that can be formed using these letters such that it does not contain the substrings ‘aaa’, ‘bbb’, or ‘ccc’. The string should contain at most a occurrences of ‘a’, at most b occurrences of ‘b’, and at most c occurrences of ‘c’.
Problem
Approach
Steps
Complexity
Input: The input consists of three integers: a, b, and c.
Example: a = 2, b = 2, c = 5
Constraints:
• 0 <= a, b, c <= 100
• a + b + c > 0
Output: The output is the longest possible happy string that satisfies the given conditions, or an empty string if no such string exists.
Example: "ccbccbcc"
Constraints:
• The string should contain at most a occurrences of 'a', b occurrences of 'b', and c occurrences of 'c'.
• The string should not contain 'aaa', 'bbb', or 'ccc' as substrings.
Goal: The goal is to construct the longest string possible with the given constraints on the occurrences of 'a', 'b', and 'c'.
Steps:
• 1. Use a priority queue to manage the counts of 'a', 'b', and 'c' in decreasing order.
• 2. Add characters to the result string, ensuring that no character appears more than twice consecutively.
• 3. After each addition, update the counts and push the characters back into the priority queue if their counts are still non-zero.
Goal: The input integers a, b, and c represent the maximum number of occurrences of 'a', 'b', and 'c' respectively. The total sum of a + b + c must be greater than 0.
Steps:
• a, b, and c are non-negative integers.
• a + b + c must be greater than 0.
Assumptions:
• It is assumed that at least one of a, b, or c is greater than zero.
• Input: Input: a = 2, b = 2, c = 5
• Explanation: "ccbccbcc" is a valid string because it respects the maximum occurrences for 'a', 'b', and 'c', and does not contain 'aaa', 'bbb', or 'ccc'.
• Input: Input: a = 3, b = 3, c = 0
• Explanation: "ababab" is the only valid string because there are no 'c' characters allowed, and it doesn't contain any invalid substrings.
Approach: We can use a greedy algorithm combined with a priority queue to keep track of the remaining counts of 'a', 'b', and 'c', ensuring we always add the most frequent character while adhering to the constraints.
Observations:
• The problem requires managing character counts while adhering to a restriction on consecutive occurrences.
• A greedy approach using a priority queue allows us to always select the character with the highest remaining count.
Steps:
• 1. Create a priority queue (max-heap) to manage the counts of 'a', 'b', and 'c'.
• 2. Pop the most frequent character and append it to the result string.
• 3. If the character was added twice, ensure the next character is different to avoid violating the rule.
• 4. Repeat the process until all characters are used or no valid string can be formed.
Empty Inputs:
• The input will always have at least one non-zero count for a, b, or c.
Large Inputs:
• Ensure the algorithm efficiently handles the case where a, b, and c are large, up to 100.
Special Values:
• Consider the case where one of a, b, or c is zero, and how the algorithm should handle this.
Constraints:
• The solution should be efficient even when a, b, and c are at their maximum values.
string longestDiverseString(int a, int b, int c) {
priority_queue<pair<int, char>, vector<pair<int, char>>, less<pair<int, char>>> pq;
if(a > 0)
pq.push({a, 'a'});
if(b > 0)
pq.push({b, 'b'});
if(c > 0)
pq.push({c, 'c'});
string res = "";
while(!pq.empty()) {
auto it = pq.top();
pq.pop();
res += string(min(2, it.first), it.second);
it.first -= min(2, it.first);
if(pq.empty()) break;
auto it2 = pq.top();
pq.pop();
res += string(min(it.first > it2.first? 1: 2, it2.first), it2.second);
it2.first -= min(it.first > it2.first? 1: 2, it2.first);
if(it.first > 0) pq.push(it);
if(it2.first > 0) pq.push(it2);
}
return res;
}
1 : Method Definition
string longestDiverseString(int a, int b, int c) {
Defines the method `longestDiverseString`, which takes three integers representing the counts of 'a', 'b', and 'c', and returns the longest string possible with no more than two consecutive characters being the same.
2 : Priority Queue Initialization
priority_queue<pair<int, char>, vector<pair<int, char>>, less<pair<int, char>>> pq;
Creates a max heap (priority queue) to store characters with their respective counts, ensuring the character with the highest count is always at the top.
3 : Condition Check for 'a'
if(a > 0)
Checks if the count of 'a' is greater than 0. If so, 'a' is pushed into the priority queue.
4 : Push 'a' to Priority Queue
pq.push({a, 'a'});
Pushes the pair containing the count of 'a' and the character 'a' into the priority queue.
5 : Condition Check for 'b'
if(b > 0)
Checks if the count of 'b' is greater than 0. If so, 'b' is pushed into the priority queue.
6 : Push 'b' to Priority Queue
pq.push({b, 'b'});
Pushes the pair containing the count of 'b' and the character 'b' into the priority queue.
7 : Condition Check for 'c'
if(c > 0)
Checks if the count of 'c' is greater than 0. If so, 'c' is pushed into the priority queue.
8 : Push 'c' to Priority Queue
pq.push({c, 'c'});
Pushes the pair containing the count of 'c' and the character 'c' into the priority queue.
9 : String Initialization
string res = "";
Initializes the result string `res`, which will be built by appending characters from the priority queue.
10 : Main Loop Start
while(!pq.empty()) {
Starts a `while` loop that continues as long as there are elements in the priority queue.
11 : Pop from Priority Queue
auto it = pq.top();
Retrieves the top element from the priority queue, which is the character with the highest remaining count.
12 : Pop from Priority Queue
pq.pop();
Removes the top element from the priority queue.
13 : Add Characters to Result
res += string(min(2, it.first), it.second);
Adds up to two characters of the top character to the result string.
14 : Decrease Count of Character
it.first -= min(2, it.first);
Decreases the count of the character after adding it to the result string.
15 : Break if Empty
if(pq.empty()) break;
Checks if the priority queue is empty. If so, the loop breaks.
16 : Pop Second Character
auto it2 = pq.top();
Retrieves the second character (with the next highest count) from the priority queue.
17 : Pop Second Character
pq.pop();
Removes the second element from the priority queue.
18 : Add Second Character to Result
res += string(min(it.first > it2.first? 1: 2, it2.first), it2.second);
Adds one or two characters of the second character to the result string, based on its remaining count.
19 : Decrease Second Character Count
it2.first -= min(it.first > it2.first? 1: 2, it2.first);
Decreases the count of the second character after adding it to the result string.
20 : Push Back Characters to Priority Queue
if(it.first > 0) pq.push(it);
If the first character still has a count greater than 0, it is pushed back into the priority queue.
21 : Push Back Characters to Priority Queue
if(it2.first > 0) pq.push(it2);
If the second character still has a count greater than 0, it is pushed back into the priority queue.
22 : Return Result
return res;
Returns the resulting string that follows the constraints.
Best Case: O(n), where n is the total sum of a, b, and c, as we process each character only once.
Average Case: O(n log 3), since the priority queue operations involve logarithmic time complexity for each insertion or extraction.
Worst Case: O(n log 3), since the priority queue is accessed a maximum of n times.
Description:
Best Case: O(1), as we do not need additional space beyond the priority queue.
Worst Case: O(3), since we only store a small number of values in the priority queue (3 values at most).
Description: The space complexity is constant because we only need to store the counts of 'a', 'b', and 'c'.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus