1304. Longest Happy String¶

Difficulty: Medium

1304. Longest Happy String

Medium

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

Solution¶

class Solution {
    static class Pair {
        char ch;
        int freq;
        public Pair(char ch, int freq) {
            this.ch = ch;
            this.freq = freq;
        }
    }
    static class sorting implements Comparator<Pair> {
        @Override
        public int compare(Pair first, Pair second) {
            return Integer.compare(second.freq, first.freq);
        }
    }
    public String longestDiverseString(int a, int b, int c) {
        PriorityQueue<Pair> pq = new PriorityQueue<>(new sorting());
        if(a > 0) pq.offer(new Pair('a' , a));
        if(b > 0) pq.offer(new Pair('b' , b));
        if(c > 0) pq.offer(new Pair('c' , c));
        String ans = "";
        int a_used = 0 , b_used = 0, c_used = 0;
        while(pq.size() > 0) {
            Pair current = pq.poll();
            if(current.ch == 'a') {
                if(a_used < 2) {
                    ans += "a";
                    current.freq--;
                    a_used++;b_used = 0; c_used = 0;
                    if(current.freq > 0) pq.offer(current);
                }
                else {
                    if(pq.size() == 0) break;
                    Pair current1 = pq.poll();
                    ans += current1.ch;
                    current1.freq--;
                    if(current1.ch == 'a') {
                        a_used++; b_used = 0; c_used = 0;
                    }
                    else if(current1.ch == 'b') {
                        b_used++; a_used = 0; c_used = 0;
                    }
                    else if(current1.ch == 'c') {
                        c_used++; a_used = 0; b_used = 0;
                    }
                    if(current.freq > 0 ) pq.offer(current);
                    if(current1.freq > 0) pq.offer(current1);
                }

            }
            else if(current.ch == 'b') {
                 if(b_used < 2) {
                    ans += "b";
                    current.freq--;
                    b_used++; a_used = 0; c_used = 0;
                    if(current.freq > 0) pq.offer(current);
                }
                else {
                    if(pq.size() == 0) break;
                    Pair current1 = pq.poll();
                    ans += current1.ch;
                    current1.freq--;
                    if(current1.ch == 'a') {
                        a_used++; b_used = 0; c_used = 0;
                    }
                    else if(current1.ch == 'b') {
                        b_used++; a_used = 0; c_used = 0;
                    }
                    else if(current1.ch == 'c') {
                        c_used++; a_used = 0; b_used = 0;
                    }
                    if(current.freq > 0 ) pq.offer(current);
                    if(current1.freq > 0) pq.offer(current1);
                }
            }
            else if(current.ch == 'c') {
                 if(c_used < 2) {
                    ans += "c";
                    current.freq--;
                    c_used++; b_used = 0; a_used = 0;
                    if(current.freq > 0) pq.offer(current);
                }
                else {
                    if(pq.size() == 0) break;
                    Pair current1 = pq.poll();
                    ans += current1.ch;
                    current1.freq--;
                    if(current1.ch == 'a') {
                        a_used++; b_used = 0; c_used = 0;
                    }
                    else if(current1.ch == 'b') {
                        b_used++; a_used = 0; c_used = 0;
                    }
                    else if(current1.ch == 'c') {
                        c_used++; a_used = 0; b_used = 0;
                    }
                    if(current.freq > 0 ) pq.offer(current);
                    if(current1.freq > 0) pq.offer(current1);
                }
            }
        }
        return ans;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here