Longest Happy String Problem

Problem

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.

Examples

Example 1:

1
2
3


Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.

Example 2:

1
2
3


Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It is the only correct answer in this case.

Solution

Method 1 - Greedy with MaxHeap

We should be greedy in using the char that occur most number of time. For eg. in eg1, we use c first, in eg.2 we use a first.

To construct the longest possible happy string while adhering to the given conditions, we need to ensure that we balance the use of ‘a’, ‘b’, and ‘c’ without letting any of them repeat more than twice consecutively. The strategy involves:

Using a Max-Heap:
- We can use a max-heap (priority queue) to always pick the letter with the highest remaining count, while ensuring that it does not form a prohibited substring (i.e., more than two consecutive appearances).
Heap Operations:
- Always try to append the character with the highest remaining count to the result.
- If the top character from the heap cannot be chosen (would form “aaa”, “bbb”, or “ccc”), select the next highest character that can be safely appended.
Balancing Counts:
- After appending a character to the result, decrease its count and reinsert it into the heap (if still available).

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64


class Solution {
	// Helper class to store character and its count
	static class Pair {
		char ch;
		int count;
	
		public Pair(Character ch, int count) {
			this.ch = ch;
			this.count = count;
		}
	}
	
	public String longestDiverseString(int a, int b, int c) {
		// Priority queue (max-heap) to store characters with their counts
		PriorityQueue<Pair> maxHeap = new PriorityQueue<>((x, y) -> Integer.compare(y.count, x.count));
		// Add all characters to the max-heap with their initial counts
		if (a > 0) {
			maxHeap.add(new Pair('a', a));
		}
		if (b > 0) {
			maxHeap.add(new Pair('b', b));
		}
		if (c > 0) {
			maxHeap.add(new Pair('c', c));
		}
		// StringBuilder to build the resulting happy string
		StringBuilder res = new StringBuilder();
		// Process characters from the max-heap to construct the string
		while (!maxHeap.isEmpty()) {
			// Pop the most frequent character
			Pair first = maxHeap.poll();
			// Check if adding this character would result in three consecutive identical characters
			int resLen = res.length();
			if (resLen >= 2 && res.charAt(resLen - 1) == first.ch && res.charAt(resLen - 2) == first.ch) {
				// If yes, we need to use the next most frequent character if available
				// No other character is available,
				if (maxHeap.isEmpty()) {
					break;
				} 
				// Get the next available character
				Pair second = maxHeap.poll();
				// Append the most frequent character to the result and reduce its availability count
				res.append(second.ch);
				second.count--;
				// If the next most frequent character still has counts left, push it back into the heap
				if (second.count > 0)  {
					maxHeap.offer(second);
				}
				// Push the initially selected character back into the heap for later use
				maxHeap.offer(first);
			} else {
				// Append the most frequent character to the result and reduce its availability count
				res.append(first.ch);
				first.count--;
				// If the character still has counts left, push it back into the heap
				if (first.count > 0) {
					maxHeap.offer(first);
				}
			}
		}
	
		return res.toString();
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        max_heap = []
        if a > 0:
            heapq.heappush(max_heap, (-a, 'a'))
        if b > 0:
            heapq.heappush(max_heap, (-b, 'b'))
        if c > 0:
            heapq.heappush(max_heap, (-c, 'c'))
        
        res = []
        
        while max_heap:
            first = heapq.heappop(max_heap)
            if len(res) >= 2 and res[-1] == res[-2] == first[1]:
                if not max_heap:
                    break
                second = heapq.heappop(max_heap)
                res.append(second[1])
                if second[0] + 1 < 0:
                    heapq.heappush(max_heap, (second[0] + 1, second[1]))
                heapq.heappush(max_heap, first)
            else:
                res.append(first[1])
                if first[0] + 1 < 0:
                    heapq.heappush(max_heap, (first[0] + 1, first[1]))

        return "".join(res)

Complexity

⏰ Time complexity: O((a + b + c) log 3) as each insertion and extraction from the heap takes O(log 3), and we’re processing all letters (a + b + c operations).
🧺 Space complexity: O(1) additional space since we’re only using a few variables and the heap’s maximum size is fixed.

Problem#

Examples#

Solution#

Method 1 - Greedy with MaxHeap#

Video explanation#

Code#

Complexity#