Longest Happy String

How it works

We can express the greedy logic recursively. At each step, we sort the characters by count (keeping the largest first) and decide how many of the most frequent character to use. If the most frequent character still dominates after using two of it, we insert one of the second character to break it up. Then we recurse on the reduced counts.

Steps

1. Define a recursive function that takes counts and characters for all three options.
2. Reorder parameters so the first character has the highest count.
3. Base case: If the second count is zero, return up to two of the first character.
4. Use up to two of the first character. If the remaining count still exceeds the second, use one of the second character.
5. Recurse with updated counts and concatenate the results.

Complexity

• Time complexity: O(n)
• Space complexity:
  • O(n) for recursion stack.
  • O(n) space for the output string.

Things to watch for

Forgetting to Track Consecutive Characters

A common mistake is only checking whether the last character matches the current one. The problem requires preventing three consecutive identical characters, not just two. You must track whether the last two characters are the same before deciding if you can add another of the same character.

Greedily Using the Same Character Without Switching

Always picking the most frequent character without considering when to switch leads to suboptimal or invalid results. When you have used the most frequent character twice in a row, you must use a different character next, even if the most frequent one still has remaining count. Failing to switch results in either an invalid string or a shorter result than possible.

Not Handling the Case When No Valid Character Exists

The algorithm must correctly terminate when no valid character can be added. This happens when all remaining characters would create three consecutive identical characters. Forgetting to handle this edge case can lead to infinite loops or incorrect outputs.

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        def rec(max1, max2, max3, char1, char2, char3):
            if max1 < max2:
                return rec(max2, max1, max3, char2, char1, char3)
            if max2 < max3:
                return rec(max1, max3, max2, char1, char3, char2)
            if max2 == 0:
                return [char1] * min(2, max1)

            use1 = min(2, max1)
            use2 = 1 if max1 - use1 >= max2 else 0
            res = [char1] * use1 + [char2] * use2
            return res + rec(max1 - use1, max2 - use2, max3, char1, char2, char3)

        return ''.join(rec(a, b, c, 'a', 'b', 'c'))

class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        vector<char> res = rec(a, b, c, 'a', 'b', 'c');
        return string(res.begin(), res.end());
    }

private:
    vector<char> rec(int max1, int max2, int max3, char char1, char char2, char char3) {
        if (max1 < max2) {
            return rec(max2, max1, max3, char2, char1, char3);
        }
        if (max2 < max3) {
            return rec(max1, max3, max2, char1, char3, char2);
        }
        if (max2 == 0) {
            vector<char> result(min(2, max1), char1);
            return result;
        }

        int use1 = min(2, max1);
        int use2 = (max1 - use1 >= max2) ? 1 : 0;

        vector<char> res(use1, char1);
        res.insert(res.end(), use2, char2);

        vector<char> rest = rec(max1 - use1, max2 - use2, max3, char1, char2, char3);
        res.insert(res.end(), rest.begin(), rest.end());

        return res;
    }
};