Longest Happy String - Complete Solution Guide

Longest Happy String is LeetCode problem 1405, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 c occurrences 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

Detailed Explanation

The problem requires constructing the longest possible string using only the characters 'a', 'b', and 'c', given the maximum number of occurrences allowed for each character (a, b, and c respectively). The constructed string must be 'happy', meaning it cannot contain substrings 'aaa', 'bbb', or 'ccc'. The goal is to return one of the longest possible happy strings or an empty string if no such string exists.

Solution Approach

The solution uses a greedy approach. At each step, it sorts the characters ('a', 'b', 'c') based on their remaining counts. The character with the highest count is selected, but only if appending it would not create a substring of three identical characters (e.g., 'aaa'). If appending the most frequent character creates such a substring, the algorithm attempts to append the next most frequent character. If no character can be appended without violating the happy string condition, the algorithm terminates and returns the constructed string.

Step-by-Step Algorithm

1. Step 1: Initialize a list/array `counts` to store the counts and characters: `[[a, 'a'], [b, 'b'], [c, 'c']]`.
2. Step 2: Initialize an empty result string `res`.
3. Step 3: Enter a `while` loop that continues as long as there's a character that can be appended.
4. Step 4: Inside the loop, sort the `counts` list/array in descending order based on the counts.
5. Step 5: Iterate through the sorted `counts`.
6. Step 6: For each character, check if its count is greater than 0. If not, it means there are no more of this character left.
7. Step 7: Check if appending the character would violate the 'happy' string condition (i.e., if the last two characters of `res` are the same as the current character). If so, continue to the next character.
8. Step 8: If the character can be appended without violating the condition, append it to `res`, decrement its count in `counts`, and set a flag `appended_something` to `True`.
9. Step 9: If `appended_something` is still `False` after iterating through all characters, it means no character could be appended without violating the condition, so break out of the `while` loop.
10. Step 10: Return the `res` string.

Key Insights

• Insight 1: A greedy approach is suitable here. Prioritize appending the character with the highest remaining count to maximize the string length.
• Insight 2: Sorting the counts of characters in each iteration is crucial to selecting the character to append, ensuring that we prioritize the character with the highest available count.
• Insight 3: The constraint of not having 'aaa', 'bbb', or 'ccc' as substrings needs to be carefully handled. We must check if the last two characters of the result are the same as the character being considered for appending, and if so, skip it to avoid creating an unhappy substring.

Complexity Analysis

Time Complexity: O(a+b+c)

Space Complexity: O(a+b+c)

Topics

This problem involves: String, Greedy, Heap (Priority Queue).

Companies

Asked at: Capgemini, EY, Geico, Rakuten, Wayfair.