Skip to main content

Heaps

Longest Happy String Solution In C++/Java/Python/Javascript

Problem Description

A string s is called happy if it satisfies the following conditions:
1. 's' only contains the letters 'a', 'b', and 'c'.
2. 's' does not contain any of "aaa", "bbb", or "ccc" as a substring.
3. 's' contains at most 'a' occurrences of the letter 'a'.
4. 's' contains at most 'b' occurrences of the letter 'b'.
5. '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

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

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

Constraints

  • 0 <= a, b, c <= 100
  • a + b + c > 0
💡
Try it Yourself First
To construct the longest happy string, count the occurrences of each character ('a', 'b', and 'c'), then prioritize the most frequent characters while ensuring no three identical characters appear consecutively. Build the string step by step, always choosing the character with the highest remaining frequency that won’t violate the rules, and construct the result efficiently.

Brute Force Approach

Intuition

To construct the longest possible string while preventing three consecutive identical characters, we must prioritize using the character with the highest count. However, if adding it would result in three identical characters in a row, we select the next most frequent character instead.

A max-heap (priority queue) is the most efficient way to manage character selection. It allows us to always pick the character with the highest remaining count while ensuring that the happy string condition is maintained.

Initially, the counts of characters 'a', 'b', and 'c' are inserted into the max heap. The character with the highest frequency is chosen first, but if using it would violate the consecutive character rule, the second most frequent character is used instead. After adding a character to the string, its count is reduced. If it still has occurrences left, it is reinserted into the heap for future use.

This approach ensures that the generated string is as long as possible while maintaining the required constraints.

Approach

Step 1: Initialize the Heap and Result String

  • Create a max-heap (priority queue) to store the counts of a, b, and c, ensuring that the most frequent character is always at the top.
  • Initialize an empty string ans to store the final result.
  • Push (a, 'a'), (b, 'b'), and (c, 'c') into the heap only if their counts are greater than 0.

Step 2: Construct the String Using the Heap

  • Repeat the process until the heap is empty:
    1. Pop the most frequent character from the heap.
    2. Check if adding this character will create three consecutive identical characters:
    • If yes, pop the second most frequent character from the heap.
    • Add this second character to ans, decrement its count, and if it still has occurrences left, push it back into the heap.
    • Push the first (most frequent) character back into the heap without using it.
  1. Otherwise, append the most frequent character to ans, decrement its count, and if it still has occurrences left, push it back into the heap.

Step 3: Return the Result String

  • Once the heap is empty and no more characters can be added, return ans as the final longest happy string.

Dry Run

Input: a = 1, b = 1, c = 7

  • We need to construct the longest happy string using the counts of 'a', 'b', and 'c', ensuring that no three consecutive characters are the same.

Step 1: Initialize Max-Heap and Result String

  • We start with the counts of characters:
  • 'a': 1
  • 'b': 1
  • 'c': 7
  • Push (count, character) pairs into a max-heap:
  • Heap = [(7, 'c'), (1, 'a'), (1, 'b')]
  • Initialize result string: ans = ""

Step 2: Build the Longest Happy String

First Selection:

  • Pop (7, 'c') → 'c' is most frequent.
  • Since ans is empty, add "cc" (max allowed consecutive count is 2).
  • Decrease 'c' count → Remaining: 5.
  • Heap = [(5, 'c'), (1, 'a'), (1, 'b')]
  • ans = "cc"

Second Selection:

  • Pop (5, 'c') → 'c' again.
  • Adding 'c' would make ccc (invalid).
  • Pick the second most frequent: Pop (1, 'a') → Add "a".
  • Decrease 'a' count → Remaining: 0.
  • Push 'c' back.
  • Heap = [(5, 'c'), (1, 'b')]
  • ans = "cca"

Third Selection:

  • Pop (5, 'c') → 'c' again.
  • Add "cc", decrement count → Remaining: 3.
  • Heap = [(3, 'c'), (1, 'b')]
  • ans = "ccacc"

Fourth Selection:

  • Pop (3, 'c') → 'c' again.
  • Adding 'c' would make ccc (invalid).
  • Pick (1, 'b') → Add "b".
  • Heap = [(3, 'c')]
  • ans = "ccaccb"

Fifth Selection:

  • Pop (3, 'c') → Add "cc", decrement count → Remaining: 1.
  • ans = "ccaccbcc"

Sixth Selection:

  • Heap = [] (Empty)
  • ans = "ccaccbccc"

Step 3: Return Final Happy String

Final Output: "ccaccbccc"

  • The longest happy string for a = 1, b = 1, c = 7 is "ccaccbcc".
Code for All Languages
C++ 
// Approach: Greedy Algorithm with Max-Heap
// Language: C++

class Solution {
public:
    // Function to generate the longest diverse string with given character counts
    string longestDiverseString(int a, int b, int c) {
        priority_queue<pair<int, char>> pq;

        // Step 1: Add available characters to the max heap
        if (a > 0) pq.push({a, 'a'});
        if (b > 0) pq.push({b, 'b'});
        if (c > 0) pq.push({c, 'c'});

        string result = "";

        // Step 2: Build the longest diverse string
        while (!pq.empty()) {
            auto [count, character] = pq.top();
            pq.pop();

            // Step 3: Check if adding the character would create three consecutive characters
            if (result.size() >= 2 && result.back() == character && result[result.size() - 2] == character) {
                if (pq.empty()) break;  // No alternative character left

                auto [nextCount, nextChar] = pq.top();
                pq.pop();

                // Add the second most frequent character to maintain diversity
                result += nextChar;
                if (--nextCount > 0) pq.push({nextCount, nextChar});

                // Push back the original character for future use
                pq.push({count, character});
            } else {
                result += character;
                if (--count > 0) pq.push({count, character});
            }
        }

        return result;
    }
};

Java 
// Approach: Greedy Algorithm with Max-Heap
// Language: Java

import java.util.PriorityQueue;
import java.util.Scanner;

class Solution {

    // Function to generate the longest diverse string with given character counts
    public String longestDiverseString(int a, int b, int c) {
        PriorityQueue<Pair> pq = new PriorityQueue<>((x, y) -> y.count - x.count);

        // Step 1: Add available characters to the max heap
        if (a > 0) pq.add(new Pair(a, 'a'));
        if (b > 0) pq.add(new Pair(b, 'b'));
        if (c > 0) pq.add(new Pair(c, 'c'));

        StringBuilder result = new StringBuilder();

        // Step 2: Build the longest diverse string
        while (!pq.isEmpty()) {
            Pair p = pq.poll();
            int count = p.count;
            char character = p.character;

            // Step 3: Check if adding the character would create three consecutive characters
            if (result.length() >= 2 && result.charAt(result.length() - 1) == character &&
                result.charAt(result.length() - 2) == character) {

                if (pq.isEmpty()) break;  // No alternative character left

                Pair temp = pq.poll();
                result.append(temp.character);
                if (--temp.count > 0) pq.add(temp);

                // Push back the original character for future use
                pq.add(p);
            } else {
                result.append(character);
                if (--count > 0) pq.add(new Pair(count, character));
            }
        }

        return result.toString();
    }

    // Helper class to store character count pairs
    static class Pair {
        int count;
        char character;

        Pair(int count, char character) {
            this.count = count;
            this.character = character;
        }
    }
}

Python 
# Approach: Greedy Algorithm with Max-Heap
# Language: Python

import heapq

class Solution(object):
    # Function to generate the longest diverse string with given character counts
    def longestDiverseString(self, a, b, c):
        """
        :type a: int
        :type b: int
        :type c: int
        :rtype: str
        """
        max_heap = []
        
        # Step 1: Add available characters to the 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'))
        
        result = []
        
        # Step 2: Build the longest diverse string
        while max_heap:
            count, char = heapq.heappop(max_heap)
            count = -count  # Convert back to positive
            
            # Step 3: Check if adding the character would create three consecutive characters
            if len(result) >= 2 and result[-1] == char and result[-2] == char:
                if not max_heap:
                    break  # No alternative character left
                
                next_count, next_char = heapq.heappop(max_heap)
                next_count = -next_count
                result.append(next_char)
                
                if next_count - 1 > 0:
                    heapq.heappush(max_heap, (-(next_count - 1), next_char))
                
                # Push back the original character for future use
                heapq.heappush(max_heap, (-count, char))
            else:
                result.append(char)
                if count - 1 > 0:
                    heapq.heappush(max_heap, (-(count - 1), char))
        
        return "".join(result)

Javascript 
/**
 * Approach: Greedy Algorithm with Max-Heap
 * Language: JavaScript
 */

/**
 * Custom Max-Heap class to handle character counts
 */
class MaxHeap {
    constructor() {
        this.heap = [];
    }

    // Insert a new element into the heap
    push(count, char) {
        if (count > 0) {
            this.heap.push({ count, char });
            this.heap.sort((a, b) => b.count - a.count); // Maintain max-heap property
        }
    }

    // Remove and return the element with the highest count
    pop() {
        return this.heap.length > 0 ? this.heap.shift() : null;
    }

    // Check if heap is empty
    isEmpty() {
        return this.heap.length === 0;
    }
}

/**
 * Function to generate the longest diverse string with given character counts
 * @param {number} a - Count of 'a'
 * @param {number} b - Count of 'b'
 * @param {number} c - Count of 'c'
 * @return {string} - Longest diverse string
 */
var longestDiverseString = function(a, b, c) {
    let maxHeap = new MaxHeap();
    
    // Step 1: Add available characters to the heap
    maxHeap.push(a, 'a');
    maxHeap.push(b, 'b');
    maxHeap.push(c, 'c');

    let result = "";

    // Step 2: Build the longest diverse string
    while (!maxHeap.isEmpty()) {
        let { count, char } = maxHeap.pop();

        // Step 3: Check if adding the character would create three consecutive characters
        if (result.length >= 2 && result[result.length - 1] === char && result[result.length - 2] === char) {
            if (maxHeap.isEmpty()) break; // No alternative character left

            let { count: nextCount, char: nextChar } = maxHeap.pop();
            result += nextChar;
            
            // Push back the updated count
            maxHeap.push(nextCount - 1, nextChar);
            maxHeap.push(count, char); // Push the original character back for future use
        } else {
            result += char;
            maxHeap.push(count - 1, char); // Reduce count and push back if still available
        }
    }

    return result;
};

Time Complexity Analysis: O(a + b + c)

Heap Operations (O(1))

  • Each operation on the priority queue (insertion or removal) takes O(log k) time, where k is the number of distinct characters. Since we have at most three characters ('a', 'b', 'c'), k = 3, so each heap operation runs in O(log 3) = O(1) time.

Iterations Over Characters (O(a + b + c))

  • In each iteration, one character is either added to the result string or skipped. Since the total number of characters is a + b + c, the loop runs at most O(a + b + c) times.

Final Time Complexity: O(1) * O(a + b + c) = O(a + b + c)

Space Complexity Analysis: O(1)

Auxiliary Space Complexity: O(1)

  • The heap contains at most three elements at any time, requiring O(1) space.
  • Other variables, such as counters and temporary storage, use only O(1) space.
  • Total Auxiliary Space Complexity: O(1)

Total Space Complexity: O(1)

  • The result string uses O(a + b + c) space, but since output storage is not counted in complexity analysis, it does not contribute to the final space complexity.

Final Space Complexity: O(1)

While the brute force approach works for small inputs, it is inefficient for larger values of a, b, and c. To optimize, we need a smarter way to construct the happy string without exploring all possibilities. This leads us to the Priority Queue (Max Heap) approach.

Optimal Approach

Intuition

We need to construct the longest possible string using three characters ('a', 'b', and 'c') while ensuring that no letter appears more than twice in a row. Instead of using a priority queue to always pick the most frequent character, we can track the counts of each letter using simple integer variables.

Since we only have three characters, using three counters (a, b, c) is enough to keep track of their remaining occurrences. Additionally, we maintain three more counters (curra, currb, currc) to track how many times a character has been added consecutively. If any of these counters reach 2, we stop adding that letter and switch to the second most-frequent letter, resetting its counter to 0.

The approach starts by identifying the character with the highest remaining count and appending it to the result string. If this character has already been used twice in a row, we select the second most-frequent character instead. If that character is also unavailable, we terminate the process since no valid letter can be added without violating the constraints. By repeating this process, we maximize the length of the string while adhering to the rules.

Approach

Step 1: Initialize Counters and Variables

  • Set curra, currb, and currc to 0. These counters track consecutive occurrences of 'a', 'b', and 'c'.
  • Compute totalIterations = a + b + c, which represents the total number of characters we can add.
  • Initialize an empty string ans to store the final result.

Step 2: Iterate Through Total Characters

  • Loop totalIterations times and determine which character to add based on frequency and consecutive constraints.

Step 3: Add 'a' If Possible

  • If 'a' has the highest remaining count and curra < 2, add 'a'.
  • If 'a' still has characters left but 'b' or 'c' has reached a consecutive limit (2), add 'a'.
  • Decrement a, increment curra, and reset currb and currc to 0.

Step 4: Add 'b' If Possible

  • If 'b' has the highest remaining count and currb < 2, add 'b'.
  • If 'b' still has characters left but 'a' or 'c' has reached a consecutive limit (2), add 'b'.
  • Decrement b, increment currb, and reset curra and currc to 0.

Step 5: Add 'c' If Possible

  • If 'c' has the highest remaining count and currc < 2, add 'c'.
  • If 'c' still has characters left but 'a' or 'b' has reached a consecutive limit (2), add 'c'.
  • Decrement c, increment currc, and reset curra and currb to 0.

Step 6: Return the Final Result

  • Once the loop completes, return ans as the longest diverse string.

Dry Run

Input: a = 1, b = 1, c = 7

  • We need to construct the longest happy string using the counts of 'a', 'b', and 'c', ensuring that no three consecutive characters are the same.

Initialization:

  • curra = 0, currb = 0, currc = 0 (Track consecutive occurrences).
  • a = 1, b = 1, c = 7
  • totalIterations = a + b + c = 1 + 1 + 7 = 9
  • ans = "" (Final result string)

Step-by-Step Execution:

Iteration 1:

  • 'c' has the highest count (c = 7).
  • currc < 2, so we add 'c' to ans.
  • Update: ans = "c", c = 6, currc = 1, curra = 0, currb = 0.

Iteration 2:

  • 'c' has the highest count (c = 6).
  • currc < 2, so we add 'c' to ans.
  • Update: ans = "cc", c = 5, currc = 2, curra = 0, currb = 0.

Iteration 3:

  • currc == 2, so we cannot add 'c'.
  • The next highest count is 'a' (a = 1).
  • We add 'a' to ans.
  • Update: ans = "cca", a = 0, curra = 1, currc = 0, currb = 0.

Iteration 4:

  • 'c' has the highest count (c = 5).
  • currc < 2, so we add 'c'.
  • Update: ans = "ccac", c = 4, currc = 1, curra = 0, currb = 0.

Iteration 5:

  • 'c' still has the highest count (c = 4).
  • currc < 2, so we add 'c' again.
  • Update: ans = "ccacc", c = 3, currc = 2, curra = 0, currb = 0.

Iteration 6:

  • currc == 2, so we cannot add 'c'.
  • The next highest count is 'b' (b = 1).
  • We add 'b' to ans.
  • Update: ans = "ccaccb", b = 0, currb = 1, curra = 0, currc = 0.

Iteration 7:

  • 'c' has the highest count (c = 3).
  • currc < 2, so we add 'c'.
  • Update: ans = "ccaccbc", c = 2, currc = 1, curra = 0, currb = 0.

Iteration 8:

  • 'c' still has the highest count (c = 2).
  • currc < 2, so we add 'c' again.
  • Update: ans = "ccaccbcc", c = 1, currc = 2, curra = 0, currb = 0.

Iteration 9:

  • currc == 2, so we cannot add 'c'.
  • No 'a' or 'b' left to break the sequence. Stop the process.

Final Result:

  • The longest happy string for a = 1, b = 1, c = 7 is "ccaccbcc".
Code for All Languages
C++ 
// Approach: Greedy Algorithm Using Counters  
// Language: C++  

class Solution {  
public:  
    // Function to generate the longest happy string
    string longestDiverseString(int a, int b, int c) {  
        int curra = 0, currb = 0, currc = 0;  
        int totalIterations = a + b + c;  
        string ans = "";  

        // Step 1: Iterate through the total number of possible characters  
        for (int i = 0; i < totalIterations; i++) {  
            // Step 2: Decide whether to add 'a'
            if ((a >= b && a >= c && curra != 2) ||  
                (a > 0 && (currb == 2 || currc == 2))) {  
                ans += 'a';  
                a--;  
                curra++;  
                currb = 0;  
                currc = 0;  
            }  
            // Step 3: Decide whether to add 'b'
            else if ((b >= a && b >= c && currb != 2) ||  
                     (b > 0 && (currc == 2 || curra == 2))) {  
                ans += 'b';  
                b--;  
                currb++;  
                curra = 0;  
                currc = 0;  
            }  
            // Step 4: Decide whether to add 'c'
            else if ((c >= a && c >= b && currc != 2) ||  
                     (c > 0 && (curra == 2 || currb == 2))) {  
                ans += 'c';  
                c--;  
                currc++;  
                curra = 0;  
                currb = 0;  
            }  
        }  

        // Step 5: Return the final happy string  
        return ans;  
    }  
};

Java 
// Approach: Greedy Algorithm Using Counters  
// Language: Java  

import java.util.Scanner;  

class Solution {  

    // Function to generate the longest happy string  
    public String longestDiverseString(int a, int b, int c) {  
        int curra = 0, currb = 0, currc = 0;  
        int totalIterations = a + b + c;  
        StringBuilder ans = new StringBuilder();  

        // Step 1: Iterate through the total number of possible characters  
        for (int i = 0; i < totalIterations; i++) {  
            // Step 2: Decide whether to add 'a'
            if ((a >= b && a >= c && curra != 2) ||  
                (a > 0 && (currb == 2 || currc == 2))) {  
                ans.append('a');  
                a--;  
                curra++;  
                currb = 0;  
                currc = 0;  
            }  
            // Step 3: Decide whether to add 'b'
            else if ((b >= a && b >= c && currb != 2) ||  
                     (b > 0 && (currc == 2 || curra == 2))) {  
                ans.append('b');  
                b--;  
                currb++;  
                curra = 0;  
                currc = 0;  
            }  
            // Step 4: Decide whether to add 'c'
            else if ((c >= a && c >= b && currc != 2) ||  
                     (c > 0 && (curra == 2 || currb == 2))) {  
                ans.append('c');  
                c--;  
                currc++;  
                curra = 0;  
                currb = 0;  
            }  
        }  

        // Step 5: Return the final happy string  
        return ans.toString();  
    }  
}

Python 
# Approach: Greedy Algorithm Using Counters  
# Language: Python  

class Solution(object):  
    def longestDiverseString(self, a, b, c):  
        """  
        :type a: int  
        :type b: int  
        :type c: int  
        :rtype: str  
        """  
        curra, currb, currc = 0, 0, 0  
        total_iterations = a + b + c  
        ans = []  

        # Step 1: Iterate through the total number of possible characters  
        for _ in range(total_iterations):  
            # Step 2: Decide whether to add 'a'
            if (a >= b and a >= c and curra != 2) or (a > 0 and (currb == 2 or currc == 2)):  
                ans.append('a')  
                a -= 1  
                curra += 1  
                currb = 0  
                currc = 0  
            # Step 3: Decide whether to add 'b'
            elif (b >= a and b >= c and currb != 2) or (b > 0 and (currc == 2 or curra == 2)):  
                ans.append('b')  
                b -= 1  
                currb += 1  
                curra = 0  
                currc = 0  
            # Step 4: Decide whether to add 'c'
            elif (c >= a and c >= b and currc != 2) or (c > 0 and (curra == 2 or currb == 2)):  
                ans.append('c')  
                c -= 1  
                currc += 1  
                curra = 0  
                currb = 0  

        # Step 5: Return the final happy string  
        return "".join(ans)

Javascript 
/**
 * Approach: Greedy Algorithm Using Counters
 * Language: JavaScript
 *
 * @param {number} a - Number of 'a' characters available.
 * @param {number} b - Number of 'b' characters available.
 * @param {number} c - Number of 'c' characters available.
 * @return {string} - Longest possible happy string.
 */
var longestDiverseString = function(a, b, c) {
    let result = [];
    let curra = 0, currb = 0, currc = 0;
    let totalIterations = a + b + c;

    // Step 1: Iterate through the total number of possible characters
    for (let i = 0; i < totalIterations; i++) {
        // Step 2: Decide whether to add 'a'
        if ((a >= b && a >= c && curra !== 2) || (a > 0 && (currb === 2 || currc === 2))) {
            result.push('a');
            a--;
            curra++;
            currb = 0;
            currc = 0;
        }
        // Step 3: Decide whether to add 'b'
        else if ((b >= a && b >= c && currb !== 2) || (b > 0 && (currc === 2 || curra === 2))) {
            result.push('b');
            b--;
            currb++;
            curra = 0;
            currc = 0;
        }
        // Step 4: Decide whether to add 'c'
        else if ((c >= a && c >= b && currc !== 2) || (c > 0 && (curra === 2 || currb === 2))) {
            result.push('c');
            c--;
            currc++;
            curra = 0;
            currb = 0;
        }
    }

    // Step 5: Return the final longest happy string
    return result.join('');
};

Time Complexity Analysis: O(a + b + c)

Iteration Over Characters (O(a + b + c))

  • We iterate up to a + b + c times, which is the total number of characters that can be added to the result string. In each iteration, we check conditions and append a character, both of which take constant time O(1).
  • Since the loop runs at most a + b + c times and each iteration is O(1), the total time complexity is O(a + b + c).

Final Time Complexity: O(a + b + c)

Space Complexity Analysis: O(1)

Auxiliary Space Complexity: O(1)

  • We use three integer counters (curra, currb, and currc) to track consecutive occurrences, which require O(1) space.
  • The final string ans uses O(a + b + c) space, but since it is part of the output and not additional storage, it is not counted in the complexity.

Total Space Complexity: O(1)

  • Total auxiliary space used remains constant, leading to an overall O(1) space complexity.

Final Space Complexity: O(1)

Learning Tip

Now we have successfully tackled this problem, let’s try these similar problems.

Reorganize String

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.Return any possible rearrangement of s or return "" if not possible.

K Frequent ElementsFirst Unique Character in a String

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.