Longest Happy String

Problem#

Given counts a, b, c for letters 'a', 'b', 'c', build the longest possible string with no three consecutive identical characters. Use only available letters.

Examples#

a = 1, b = 1, c = 7 → "ccaccbcc" (length 7)
a = 7, b = 1, c = 0 → "aabaa"

Constraints#

0 <= a, b, c <= 100.

Hints#

Hint 1

Always pick the most-remaining letter — unless it would make a triple, in which case pick the next most.

Approach#

Max-heap of (count, char). Each step: pop top; if appending it would create a triple, pop the second instead. Push remaining back. Stop when heap is empty or the only candidate would form a triple.

Solution#

class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        priority_queue<pair<int,char>> pq;
        if (a) pq.push({a, 'a'});
        if (b) pq.push({b, 'b'});
        if (c) pq.push({c, 'c'});
        string out;
        while (!pq.empty()) {
            auto [cnt, ch] = pq.top(); pq.pop();
            int n = (int)out.size();
            if (n >= 2 && out[n-1] == ch && out[n-2] == ch) {
                if (pq.empty()) break;
                auto [cnt2, ch2] = pq.top(); pq.pop();
                out += ch2;
                if (--cnt2) pq.push({cnt2, ch2});
                pq.push({cnt, ch});
            } else {
                out += ch;
                if (--cnt) pq.push({cnt, ch});
            }
        }
        return out;
    }
};

import "container/heap"

type happyItem struct {
    cnt int
    ch  byte
}

type happyHeap []happyItem

func (h happyHeap) Len() int            { return len(h) }
func (h happyHeap) Less(i, j int) bool  { return h[i].cnt > h[j].cnt }
func (h happyHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *happyHeap) Push(x interface{}) { *h = append(*h, x.(happyItem)) }
func (h *happyHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

func longestDiverseString(a int, b int, c int) string {
    h := &happyHeap{}
    heap.Init(h)
    if a > 0 {
        heap.Push(h, happyItem{a, 'a'})
    }
    if b > 0 {
        heap.Push(h, happyItem{b, 'b'})
    }
    if c > 0 {
        heap.Push(h, happyItem{c, 'c'})
    }
    out := []byte{}
    for h.Len() > 0 {
        top := heap.Pop(h).(happyItem)
        n := len(out)
        if n >= 2 && out[n-1] == top.ch && out[n-2] == top.ch {
            if h.Len() == 0 {
                break
            }
            second := heap.Pop(h).(happyItem)
            out = append(out, second.ch)
            second.cnt--
            if second.cnt > 0 {
                heap.Push(h, second)
            }
            heap.Push(h, top)
        } else {
            out = append(out, top.ch)
            top.cnt--
            if top.cnt > 0 {
                heap.Push(h, top)
            }
        }
    }
    return string(out)
}

import heapq

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        pq = []
        if a > 0:
            heapq.heappush(pq, (-a, 'a'))
        if b > 0:
            heapq.heappush(pq, (-b, 'b'))
        if c > 0:
            heapq.heappush(pq, (-c, 'c'))
        out = []
        while pq:
            cnt, ch = heapq.heappop(pq)
            cnt = -cnt
            n = len(out)
            if n >= 2 and out[-1] == ch and out[-2] == ch:
                if not pq:
                    break
                cnt2, ch2 = heapq.heappop(pq)
                cnt2 = -cnt2
                out.append(ch2)
                cnt2 -= 1
                if cnt2 > 0:
                    heapq.heappush(pq, (-cnt2, ch2))
                heapq.heappush(pq, (-cnt, ch))
            else:
                out.append(ch)
                cnt -= 1
                if cnt > 0:
                    heapq.heappush(pq, (-cnt, ch))
        return "".join(out)

class MaxHeap {
    constructor() { this.h = []; }
    size() { return this.h.length; }
    push(item) {
        this.h.push(item);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p].cnt < this.h[i].cnt) {
                [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
                i = p;
            } else break;
        }
    }
    pop() {
        if (this.h.length === 0) return undefined;
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length > 0) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let best = i;
                if (l < n && this.h[l].cnt > this.h[best].cnt) best = l;
                if (r < n && this.h[r].cnt > this.h[best].cnt) best = r;
                if (best === i) break;
                [this.h[i], this.h[best]] = [this.h[best], this.h[i]];
                i = best;
            }
        }
        return top;
    }
}

function longestDiverseString(a, b, c) {
    const pq = new MaxHeap();
    if (a > 0) pq.push({ cnt: a, ch: 'a' });
    if (b > 0) pq.push({ cnt: b, ch: 'b' });
    if (c > 0) pq.push({ cnt: c, ch: 'c' });
    let out = '';
    while (pq.size() > 0) {
        const top = pq.pop();
        const n = out.length;
        if (n >= 2 && out[n - 1] === top.ch && out[n - 2] === top.ch) {
            if (pq.size() === 0) break;
            const second = pq.pop();
            out += second.ch;
            second.cnt--;
            if (second.cnt > 0) pq.push(second);
            pq.push(top);
        } else {
            out += top.ch;
            top.cnt--;
            if (top.cnt > 0) pq.push(top);
        }
    }
    return out;
}

class Solution {
    public String longestDiverseString(int a, int b, int c) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> y[0] - x[0]);
        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 out = new StringBuilder();
        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int n = out.length();
            char ch = (char) top[1];
            if (n >= 2 && out.charAt(n - 1) == ch && out.charAt(n - 2) == ch) {
                if (pq.isEmpty()) break;
                int[] second = pq.poll();
                out.append((char) second[1]);
                second[0]--;
                if (second[0] > 0) pq.offer(second);
                pq.offer(top);
            } else {
                out.append(ch);
                top[0]--;
                if (top[0] > 0) pq.offer(top);
            }
        }
        return out.toString();
    }
}

interface HappyItem {
    cnt: number;
    ch: string;
}

class MaxHeap {
    private h: HappyItem[] = [];
    size(): number { return this.h.length; }
    push(item: HappyItem): void {
        this.h.push(item);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p].cnt < this.h[i].cnt) {
                [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
                i = p;
            } else break;
        }
    }
    pop(): HappyItem | undefined {
        if (this.h.length === 0) return undefined;
        const top = this.h[0];
        const last = this.h.pop() as HappyItem;
        if (this.h.length > 0) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let best = i;
                if (l < n && this.h[l].cnt > this.h[best].cnt) best = l;
                if (r < n && this.h[r].cnt > this.h[best].cnt) best = r;
                if (best === i) break;
                [this.h[i], this.h[best]] = [this.h[best], this.h[i]];
                i = best;
            }
        }
        return top;
    }
}

function longestDiverseString(a: number, b: number, c: number): string {
    const pq = new MaxHeap();
    if (a > 0) pq.push({ cnt: a, ch: 'a' });
    if (b > 0) pq.push({ cnt: b, ch: 'b' });
    if (c > 0) pq.push({ cnt: c, ch: 'c' });
    let out = '';
    while (pq.size() > 0) {
        const top = pq.pop() as HappyItem;
        const n = out.length;
        if (n >= 2 && out[n - 1] === top.ch && out[n - 2] === top.ch) {
            if (pq.size() === 0) break;
            const second = pq.pop() as HappyItem;
            out += second.ch;
            second.cnt--;
            if (second.cnt > 0) pq.push(second);
            pq.push(top);
        } else {
            out += top.ch;
            top.cnt--;
            if (top.cnt > 0) pq.push(top);
        }
    }
    return out;
}

Editorial#

Greedy on the most-remaining letter would create triples; the fix is “if a triple is imminent, take a different letter for one step”. The heap returns the second-largest reliably. With three letters, the heap has size ≤ 3, so each operation is effectively O(1).

Complexity#

Time: O(a + b + c).
Space: O(1).

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#