Using greedy without proof
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.
Move from brute-force thinking to an efficient approach using greedy strategy.
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 <= 100a + b + c > 0Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Greedy
1 1 7
7 1 0
reorganize-string)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #1405: Longest Happy String
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();
}
}
// Accepted solution for LeetCode #1405: Longest Happy String
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 any) { *a = append(*a, x.(pair)) }
func (a *hp) Pop() any { 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)
}
# Accepted solution for LeetCode #1405: Longest Happy String
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)
// Accepted solution for LeetCode #1405: Longest Happy String
struct Solution;
use std::collections::BinaryHeap;
impl Solution {
fn longest_diverse_string(a: i32, b: i32, c: i32) -> String {
let mut queue: BinaryHeap<(i32, char)> = BinaryHeap::new();
if a > 0 {
queue.push((a, 'a'));
}
if b > 0 {
queue.push((b, 'b'));
}
if c > 0 {
queue.push((c, 'c'));
}
let mut res = "".to_string();
while !queue.is_empty() {
match queue.len() {
1 => {
let (size, c) = queue.pop().unwrap();
for _ in 0..2.min(size) {
res.push(c);
}
}
_ => {
let (mut size_a, char_a) = queue.pop().unwrap();
let (mut size_b, char_b) = queue.pop().unwrap();
for _ in 0..2.min(size_a) {
res.push(char_a);
size_a -= 1;
}
if size_b > size_a {
for _ in 0..2.min(size_b) {
res.push(char_b);
size_b -= 1;
}
} else {
res.push(char_b);
size_b -= 1;
}
if size_a > 0 {
queue.push((size_a, char_a));
}
if size_b > 0 {
queue.push((size_b, char_b));
}
}
}
}
res
}
}
#[test]
fn test() {
let a = 7;
let b = 1;
let c = 0;
let res = "aabaa".to_string();
assert_eq!(Solution::longest_diverse_string(a, b, c), res);
}
// Accepted solution for LeetCode #1405: Longest Happy String
function longestDiverseString(a: number, b: number, c: number): string {
const pq = new PriorityQueue<number[]>((a, b) => b[1] - a[1]);
if (a > 0) pq.enqueue(['a'.charCodeAt(0), a]);
if (b > 0) pq.enqueue(['b'.charCodeAt(0), b]);
if (c > 0) pq.enqueue(['c'.charCodeAt(0), c]);
const sb: number[] = [];
while (!pq.isEmpty()) {
const cur = pq.dequeue();
const n = sb.length;
if (n >= 2 && sb[n - 1] === cur[0] && sb[n - 2] === cur[0]) {
if (pq.isEmpty()) break;
const next = pq.dequeue();
sb.push(next[0]);
if (next[1] > 1) {
next[1]--;
pq.enqueue(next);
}
pq.enqueue(cur);
} else {
sb.push(cur[0]);
if (cur[1] > 1) {
cur[1]--;
pq.enqueue(cur);
}
}
}
return String.fromCharCode(...sb);
}
Use this to step through a reusable interview workflow for this problem.
Try every possible combination of choices. With n items each having two states (include/exclude), the search space is 2ⁿ. Evaluating each combination takes O(n), giving O(n × 2ⁿ). The recursion stack or subset storage uses O(n) space.
Greedy algorithms typically sort the input (O(n log n)) then make a single pass (O(n)). The sort dominates. If the input is already sorted or the greedy choice can be computed without sorting, time drops to O(n). Proving greedy correctness (exchange argument) is harder than the implementation.
Review these before coding to avoid predictable interview regressions.
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.