Formatted question description: https://leetcode.ca/all/1405.html

1405. Longest Happy String (Medium)

A string is called happy if it does not have any of the strings 'aaa', 'bbb' or 'ccc' as a substring.

Given three integers a, b and c, return any string s, which satisfies following conditions:

  • s is happy and longest possible.
  • s contains at most a occurrences of the letter 'a', at most b occurrences of the letter 'b' and at most c occurrences of the letter 'c'.
  • will only contain 'a', 'b' and 'c' letters.

If there is no such string s return the empty string "".

 

Example 1:

Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.

Example 2:

Input: a = 2, b = 2, c = 1
Output: "aabbc"

Example 3:

Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It's the only correct answer in this case.

 

Constraints:

  • 0 <= a, b, c <= 100
  • a + b + c > 0

Related Topics:
Dynamic Programming, Greedy

Solution 1.

// OJ: https://leetcode.com/problems/longest-happy-string/

// Time: O(A+B+C)
// Space: O(1)
class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        int cnt[3] = {a, b, c}, prev = -1;
        string ans;
        while (true) {
            int maxIndex = -1;
            for (int i = 0; i < 3; ++i) {
                if (i != prev && (maxIndex == -1 || cnt[i] > cnt[maxIndex])) maxIndex = i;
            }
            if (cnt[maxIndex] == 0) break;
            int num = min(2, cnt[maxIndex]);
            if (prev != -1 && cnt[prev] > cnt[maxIndex]) num = 1;
            cnt[maxIndex] -= num;
            while (num--) ans.push_back(maxIndex + 'a');
            prev = maxIndex;
        }
        return ans;
    }
};

Java

class Solution {
    public String longestDiverseString(int a, int b, int c) {
        PriorityQueue<LetterCount> priorityQueue = new PriorityQueue<LetterCount>();
        if (a > 0)
            priorityQueue.offer(new LetterCount('a', a));
        if (b > 0)
            priorityQueue.offer(new LetterCount('b', b));
        if (c > 0)
            priorityQueue.offer(new LetterCount('c', c));
        StringBuffer sb = new StringBuffer();
        char prevLetter = 'z';
        int prevCount = 0;
        while (!priorityQueue.isEmpty()) {
            LetterCount letterCount = priorityQueue.poll();
            char letter = letterCount.letter;
            int count = letterCount.count;
            if (letter == prevLetter) {
                if (prevCount < 2) {
                    int curCount = Math.min(count, 2 - prevCount);
                    for (int i = 0; i < curCount; i++)
                        sb.append(letter);
                    prevCount += curCount;
                    letterCount.count -= curCount;
                    if (letterCount.count > 0)
                        priorityQueue.offer(letterCount);
                } else {
                    if (priorityQueue.isEmpty())
                        break;
                    LetterCount letterCount2 = priorityQueue.poll();
                    sb.append(letterCount2.letter);
                    letterCount2.count--;
                    if (letterCount2.count > 0)
                        priorityQueue.offer(letterCount2);
                    priorityQueue.offer(letterCount);
                    prevLetter = letterCount2.letter;
                    prevCount = 1;
                }
            } else {
                int curCount = Math.min(count, 2);
                for (int i = 0; i < curCount; i++)
                    sb.append(letter);
                letterCount.count -= curCount;
                if (letterCount.count > 0)
                    priorityQueue.offer(letterCount);
                prevLetter = letter;
                prevCount = curCount;
            }
        }
        return sb.toString();
    }
}

class LetterCount implements Comparable<LetterCount> {
    char letter;
    int count;

    public LetterCount(char letter, int count) {
        this.letter = letter;
        this.count = count;
    }

    public int compareTo(LetterCount letterCount2) {
        if (this.count != letterCount2.count)
            return letterCount2.count - this.count;
        else
            return this.letter - letterCount2.letter;
    }
}

All Problems

All Solutions