Longest Happy String
The drill: Build the longest possible string from up to a copies of 'a', b copies of 'b', and c copies of 'c' with no letter ever running three in a row — any longest valid string is accepted.
Three counts arrive — how many 'a', 'b', and 'c' characters are available — and the job is building the longest string possible using no more of each letter than its given count.
The one hard rule is no letter may appear three times in a row anywhere in the string; using fewer than the maximum available copies of a letter is always allowed if the streak rule demands it.
Multiple longest strings can be equally valid for the same input, and any one of them is accepted as long as it hits the maximum achievable length and never triples a letter.
- each of a, b, c can range from zero up to a few hundred
- no letter may repeat three times consecutively
- using fewer copies of a letter than available is always allowed
- any string reaching the maximum possible length is accepted
HINT 1 THE NUDGE
Whichever letter has the most copies left is usually the safest one to place next — greedily grabbing it keeps the other letters' options open longest.
HINT 2 THE STRUCTURE
The only time greedy backs off the top letter is when placing it would make three in a row — then borrowing one copy of the next-most-available letter breaks the streak without wasting anything.
HINT 3 ONE STEP FROM THE ANSWER
Keep the three remaining counts in a max-heap. Pop the largest; if it would make a triple, pop the second-largest and place that instead, pushing the skipped one back in for next time.
Counts start a=0, b=5, c=2 — always place the most-plentiful letter unless it would make three in a row.
class Solution:
def longestDiverseString(self, a: int, b: int, c: int) -> str:
heap = []
for ch, cnt in zip("abc", (a, b, c)):
if cnt > 0:
heapq.heappush(heap, (-cnt, ch))
result = []
while heap:
cnt, ch = heapq.heappop(heap)
cnt = -cnt
if len(result) >= 2 and result[-1] == result[-2] == ch:
if not heap:
break
cnt2, ch2 = heapq.heappop(heap)
cnt2 = -cnt2
result.append(ch2)
cnt2 -= 1
if cnt2 > 0:
heapq.heappush(heap, (-cnt2, ch2))
heapq.heappush(heap, (-cnt, ch))
else:
result.append(ch)
cnt -= 1
if cnt > 0:
heapq.heappush(heap, (-cnt, ch))
return "".join(result)class Solution:
def longestDiverseString(self, a: int, b: int, c: int) -> str:
counts = {"a": a, "b": b, "c": c}
result = []
while True:
candidates = sorted(counts, key=lambda ch: -counts[ch]) # just compare the three counts
placed = False
for ch in candidates:
if counts[ch] == 0:
continue
if len(result) >= 2 and result[-1] == result[-2] == ch:
continue
result.append(ch)
counts[ch] -= 1
placed = True
break
if not placed:
break
return "".join(result)class Solution {
public String longestDiverseString(int a, int b, int c) {
char[] chars = { 'a', 'b', 'c' };
int[] counts = { a, b, c };
PriorityQueue<int[]> heap = new PriorityQueue<>((x, y) -> y[1] - x[1]); // [charIndex, count]
for (int i = 0; i < 3; i++) {
if (counts[i] > 0) {
heap.offer(new int[] { i, counts[i] });
}
}
StringBuilder sb = new StringBuilder();
while (!heap.isEmpty()) {
int[] top = heap.poll();
boolean wouldTriple = sb.length() >= 2
&& sb.charAt(sb.length() - 1) == chars[top[0]]
&& sb.charAt(sb.length() - 2) == chars[top[0]];
if (wouldTriple) {
if (heap.isEmpty()) {
break;
}
int[] second = heap.poll();
sb.append(chars[second[0]]);
second[1]--;
if (second[1] > 0) {
heap.offer(second);
}
heap.offer(top);
} else {
sb.append(chars[top[0]]);
top[1]--;
if (top[1] > 0) {
heap.offer(top);
}
}
}
return sb.toString();
}
}class Solution {
public String longestDiverseString(int a, int b, int c) {
int[] counts = { a, b, c };
char[] chars = { 'a', 'b', 'c' };
StringBuilder sb = new StringBuilder();
while (true) {
int best = -1;
for (int i = 0; i < 3; i++) {
if (counts[i] == 0) {
continue;
}
boolean wouldTriple = sb.length() >= 2
&& sb.charAt(sb.length() - 1) == chars[i]
&& sb.charAt(sb.length() - 2) == chars[i];
if (wouldTriple) {
continue;
}
if (best == -1 || counts[i] > counts[best]) {
best = i;
}
}
if (best == -1) {
break;
}
sb.append(chars[best]);
counts[best]--;
}
return sb.toString();
}
}✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED