Welcome to Subscribe On Youtube

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.

  • 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;
        }
    }
    
    ############
    
    class Solution {
        public String longestDiverseString(int a, int b, int c) {
            Queue<int[]> pq = new PriorityQueue<>((x, y) -> y[1] - x[1]);
            if (a > 0) {
                pq.offer(new int[] {'a', a});
            }
            if (b > 0) {
                pq.offer(new int[] {'b', b});
            }
            if (c > 0) {
                pq.offer(new int[] {'c', c});
            }
    
            StringBuilder sb = new StringBuilder();
            while (pq.size() > 0) {
                int[] cur = pq.poll();
                int n = sb.length();
                if (n >= 2 && sb.codePointAt(n - 1) == cur[0] && sb.codePointAt(n - 2) == cur[0]) {
                    if (pq.size() == 0) {
                        break;
                    }
                    int[] next = pq.poll();
                    sb.append((char) next[0]);
                    if (next[1] > 1) {
                        next[1]--;
                        pq.offer(next);
                    }
                    pq.offer(cur);
                } else {
                    sb.append((char) cur[0]);
                    if (cur[1] > 1) {
                        cur[1]--;
                        pq.offer(cur);
                    }
                }
            }
    
            return sb.toString();
        }
    }
    
    
  • // 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;
        }
    };
    
  • class Solution:
        def longestDiverseString(self, a: int, b: int, c: int) -> str:
            h = []
            if a > 0:
                heappush(h, [-a, 'a'])
            if b > 0:
                heappush(h, [-b, 'b'])
            if c > 0:
                heappush(h, [-c, 'c'])
    
            ans = []
            while len(h) > 0:
                cur = heappop(h)
                if len(ans) >= 2 and ans[-1] == cur[1] and ans[-2] == cur[1]:
                    if len(h) == 0:
                        break
                    nxt = heappop(h)
                    ans.append(nxt[1])
                    if -nxt[0] > 1:
                        nxt[0] += 1
                        heappush(h, nxt)
                    heappush(h, cur)
                else:
                    ans.append(cur[1])
                    if -cur[0] > 1:
                        cur[0] += 1
                        heappush(h, cur)
    
            return ''.join(ans)
    
    ############
    
    class Solution:
        def longestDiverseString(self, a: int, b: int, c: int) -> str:
            d = [[a, "a"], [b, "b"], [c, "c"]]
            total = a + b + c
            res = ""
            def canAdd(res, x):
                return len(res) < 2 or res[-1] != x or res[-2] != x
            while total > 0:
                d.sort(reverse=True)
                for i, (count, char) in enumerate(d):
                    if count == 0: continue
                    if canAdd(res, char):
                        res += char
                        d[i][0] -= 1
                        total -= 1
                        break
                else:
                    break
            return res
    
  • type pair struct {
    	c   byte
    	num int
    }
    
    type hp []pair
    
    func (a hp) Len() int            { return len(a) }
    func (a hp) Swap(i, j int)       { a[i], a[j] = a[j], a[i] }
    func (a hp) Less(i, j int) bool  { return a[i].num > a[j].num }
    func (a *hp) Push(x interface{}) { *a = append(*a, x.(pair)) }
    func (a *hp) Pop() interface{}   { l := len(*a); t := (*a)[l-1]; *a = (*a)[:l-1]; return t }
    
    func longestDiverseString(a int, b int, c int) string {
    	var h hp
    	if a > 0 {
    		heap.Push(&h, pair{'a', a})
    	}
    	if b > 0 {
    		heap.Push(&h, pair{'b', b})
    	}
    	if c > 0 {
    		heap.Push(&h, pair{'c', c})
    	}
    
    	var ans []byte
    	for len(h) > 0 {
    		cur := heap.Pop(&h).(pair)
    		if len(ans) >= 2 && ans[len(ans)-1] == cur.c && ans[len(ans)-2] == cur.c {
    			if len(h) == 0 {
    				break
    			}
    			next := heap.Pop(&h).(pair)
    			ans = append(ans, next.c)
    			if next.num > 1 {
    				next.num--
    				heap.Push(&h, next)
    			}
    			heap.Push(&h, cur)
    		} else {
    			ans = append(ans, cur.c)
    			if cur.num > 1 {
    				cur.num--
    				heap.Push(&h, cur)
    			}
    		}
    	}
    
    	return string(ans)
    }
    
    
  • function longestDiverseString(a: number, b: number, c: number): string {
        let ans = [];
        let store: Array<[string, number]> = [
            ['a', a],
            ['b', b],
            ['c', c],
        ];
        while (true) {
            store.sort((a, b) => b[1] - a[1]);
            let hasNext = false;
            for (let [i, [ch, ctn]] of store.entries()) {
                if (ctn < 1) {
                    break;
                }
                const n = ans.length;
                if (n >= 2 && ans[n - 1] == ch && ans[n - 2] == ch) {
                    continue;
                }
                hasNext = true;
                ans.push(ch);
                store[i][1] -= 1;
                break;
            }
            if (!hasNext) {
                break;
            }
        }
        return ans.join('');
    }
    
    

All Problems

All Solutions