This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE
1405. Longest Happy String
Difficulty: Medium
Topics: String, Greedy, Heap (Priority Queue)
A string s is called happy if it satisfies the following conditions:
-
sonly contains the letters'a','b', and'c'. -
sdoes not contain any of"aaa","bbb", or"ccc"as a substring. -
scontains at mostaoccurrences of the letter'a'. -
scontains at mostboccurrences of the letter'b'. -
s contains at mostcoccurrences 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 <= 100a + b + c > 0
Hint:
- Use a greedy approach.
- Use the letter with the maximum current limit that can be added without breaking the condition.
Solution:
We can employ a greedy algorithm. The approach is based on the following steps:
-
Use a Priority Queue (Max Heap):
- We can use a max heap to keep track of the characters and their remaining counts. This allows us to always choose the character with the highest remaining count while ensuring that we don't exceed two consecutive occurrences of the same character.
-
Construct the String:
- Continuously extract the character with the highest count from the heap and append it to the result string.
- If the last two characters in the result string are the same, we cannot append the same character again. Instead, we will append the next character with the highest count.
- If we can append a character, we reduce its count and continue the process.
-
Return the Result:
- If at any point we can't append a character without breaking the happy string conditions, we stop the process.
Let's implement this solution in PHP: 1405. Longest Happy String
`php
<?php
/**
- @param Integer $a
- @param Integer $b
- @param Integer $c
- @return String
/
function longestHappyString($a, $b, $c) {
...
...
...
/*
- go to ./solution.php */ }
// Example usage
$a1 = 1; $b1 = 1; $c1 = 7;
echo "Input: a = $a1, b = $b1, c = $c1\n";
echo "Output: " . longestHappyString($a1, $b1, $c1) . "\n"; // Output: "ccaccbcc" or similar
$a2 = 7; $b2 = 1; $c2 = 0;
echo "Input: a = $a2, b = $b2, c = $c2\n";
echo "Output: " . longestHappyString($a2, $b2, $c2) . "\n"; // Output: "aabaa"
?>
`
Explanation:
-
Max Heap Creation:
- We initialize an array
$maxHeapwith the counts of characters'a','b', and'c'.
- We initialize an array
-
Sorting the Heap:
- We use
usortto sort the heap based on the remaining counts in descending order.
- We use
-
Building the Result String:
- While there are characters in the heap:
- Sort the heap to ensure we always access the character with the highest count.
- If the last two characters in the result string are the same as the character with the highest count, we need to check if we can add a different character.
- If we can add the character, we decrement its count and continue.
- While there are characters in the heap:
-
Return:
- Finally, we return the constructed happy string.
Complexity Analysis
- Time Complexity: The solution runs in O(n log m) where n is the total number of characters we might output (i.e., a + b + c), and m is the number of different characters (which is at most 3).
- Space Complexity: The space complexity is O(1) for the counts since we only keep a constant number of characters in the heap.
This solution efficiently constructs the longest happy string while adhering to the constraints specified in the problem.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE
MD ARIFUL HAQUE | Sciencx (2024-10-16T01:14:11+00:00) 1405. Longest Happy String. Retrieved from https://www.scien.cx/2024/10/16/1405-longest-happy-string/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.