1405. Longest Happy String

[mah-shamim]

Topics: String, Greedy, Heap (Priority Queue)

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 most a occurrences of the letter 'a'.
• s contains at most b occurrences of the letter 'b'.
• s contains at most coccurrences 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 <= 100
• a + b + c > 0

Hint:

1. Use a greedy approach.
2. Use the letter with the maximum current limit that can be added without breaking the condition.

[kovatz]

We can employ a greedy algorithm. The approach is based on the following steps:

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

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

3. 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
/**
 * @param Integer $a
 * @param Integer $b
 * @param Integer $c
 * @return String
 */
function longestHappyString($a, $b, $c) {
    // Create a max heap to store character counts
    $maxHeap = [];
    if ($a > 0) $maxHeap[] = ['char' => 'a', 'count' => $a];
    if ($b > 0) $maxHeap[] = ['char' => 'b', 'count' => $b];
    if ($c > 0) $maxHeap[] = ['char' => 'c', 'count' => $c];

    // Sort the heap based on count (max heap)
    usort($maxHeap, function($x, $y) {
        return $y['count'] - $x['count'];
    });

    $result = '';
    
    while (count($maxHeap) > 0) {
        // Sort the heap to get the character with the highest count
        usort($maxHeap, function($x, $y) {
            return $y['count'] - $x['count'];
        });

        // Get the character with the highest count
        $first = array_shift($maxHeap); // Most frequent character
        if (strlen($result) >= 2 && $result[-1] == $first['char'] && $result[-2] == $first['char']) {
            // We can't add this character because it would create 3 in a row
            if (count($maxHeap) == 0) break; // No other character to add

            // Get the second character
            $second = array_shift($maxHeap);
            $result .= $second['char'];
            $second['count']--;
            if ($second['count'] > 0) {
                $maxHeap[] = $second; // Add it back if there's more left
            }
            // Put the first character back
            $maxHeap[] = $first; // Add the first character back
        } else {
            // We can add the first character
            $result .= $first['char'];
            $first['count']--;
            if ($first['count'] > 0) {
                $maxHeap[] = $first; // Add it back if there's more left
            }
        }
    }

    return $result;
}

// 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:

1. Max Heap Creation:

   • We initialize an array $maxHeap with the counts of characters 'a', 'b', and 'c'.

2. Sorting the Heap:

   • We use usort to sort the heap based on the remaining counts in descending order.

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

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

[mah-shamim]

Thanks To solve the problem of generating the longest happy string with the given constraints on the counts of characters 'a', 'b', and 'c'

[kovatz]

Thanks