Jobs

Interviews

Discussions

Longest Happy String #13 Most Asked

Medium

Capgemini

1 view

Topics:

StringsGreedy Algorithms

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 <= 100
a + b + c > 0

Try coding it in LeetCode

Longest Happy String #13 Most Asked

Medium

Capgemini

1 view

Topics:

StringsGreedy Algorithms

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'.

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 <= 100
a + b + c > 0

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the input integers a, b, and c? Can they be zero, and what is their maximum possible value?
Is it possible for the input to be such that no non-empty happy string can be formed, for example, if two of the counts are zero? If so, what should be returned?
The problem asks for 'the' longest happy string. If there are multiple strings of the same maximum length, is any one of them acceptable?
Just to be certain about the definition of 'happy', does the rule against three consecutive characters apply only to 'aaa', 'bbb', and 'ccc', or could there be other characters involved in a more general version of this problem?
If one character count is significantly larger than the sum of the other two, for instance, a = 100, b = 1, c = 1, will there be a case where we can't use all the characters?

Brute Force Solution

Approach

To find the longest possible string without any triple letters, the brute force approach is to build every single possible string using the letters we have. After creating all combinations, we check each one to see if it follows the 'no three in a row' rule and then pick the longest one that does.

Here's how the algorithm would work step-by-step:

First, imagine all the letters 'a', 'b', and 'c' we have available.
Start building a string by picking one letter at a time.
At each step of building the string, we have a choice of which letter to add next from the ones we still have left.
We need to explore every single path of choices. For example, after picking 'a', we could then pick another 'a', or a 'b', or a 'c'.
We continue this process of adding one letter at a time, trying every possible sequence, until we have used up all the letters.
This creates a massive list of every possible arrangement of the given letters.
Now, go through this entire list of generated strings one by one.
For each string, check if it's 'happy' – meaning, it doesn't have 'aaa', 'bbb', or 'ccc' anywhere inside it.
Keep track of all the strings that pass this check.
Finally, from the collection of all 'happy' strings, find the longest one and that's our answer.

Code Implementation

def longestHappyString(a_count: int, b_count: int, c_count: int) -> str:
    all_possible_happy_strings = []

    def generate_strings(current_string, remaining_a, remaining_b, remaining_c):
        # A string is a candidate for the final list once we've exhausted one or more characters.
        if len(current_string) > 1:
            all_possible_happy_strings.append(current_string)

        # Explore adding 'a' if it's available and doesn't create 'aaa'.
        if remaining_a > 0 and not current_string.endswith('aa'):
            generate_strings(current_string + 'a', remaining_a - 1, remaining_b, remaining_c)

        # Explore adding 'b' if it's available and doesn't create 'bbb'.
        if remaining_b > 0 and not current_string.endswith('bb'):
            generate_strings(current_string + 'b', remaining_a, remaining_b - 1, remaining_c)

        # Explore adding 'c' if it's available and doesn't create 'ccc'.
        if remaining_c > 0 and not current_string.endswith('cc'):
            generate_strings(current_string + 'c', remaining_a, remaining_b, remaining_c - 1)

    generate_strings("", a_count, b_count, c_count)

    longest_string_found = ""
    for candidate_string in all_possible_happy_strings:
        if len(candidate_string) > len(longest_string_found):
            longest_string_found = candidate_string

    # After checking all generated happy strings, return the one with the maximum length.
    return longest_string_found

Big(O) Analysis

Time Complexity

O(3^n * n) – The brute force approach generates all possible strings by making a choice at each step from the available 'a's, 'b's, and 'c's. If the total number of letters is n, this creates a decision tree where each node can have up to 3 branches, leading to a number of permutations that grows exponentially, roughly on the order of 3^n. For each of these generated strings of length up to n, we must then perform a check to see if it's 'happy', which involves iterating through the string, taking O(n) time. Therefore, the total time complexity is dominated by generating and then checking all these strings, which is approximately O(3^n * n).

Space Complexity

O(N! * N) – The brute force approach requires generating and storing every possible arrangement of the given letters. If the total number of letters is N (sum of a, b, and c), the number of permutations is on the order of N factorial. Since each of these N! strings has a length of N, the total space needed for the list of all generated strings is O(N! * N). Additionally, the recursive exploration of every single path of choices creates a call stack that could go as deep as N, contributing O(N) space, but this is dominated by the storage of the permutations.

Optimal Solution

Approach

The best way to build the longest possible string without having three identical characters in a row is to be greedy. At each step, we'll add the character we have the most of, but we'll be careful not to add it if it would break the rule.

Here's how the algorithm would work step-by-step:

First, figure out which character ('a', 'b', or 'c') you have the most of.
Try to add two of that most frequent character to our result string. This is the fastest way to use up characters.
Before adding them, check if the last two characters of our result string are already the same as the one we're about to add. If they are, we can't add this character right now.
If we can't add the most common character, look at the second-most common character and try to add just one of that to our string instead.
After adding a character (or two), update the remaining counts for 'a', 'b', and 'c'.
Repeat this process of picking the most frequent available character and adding it carefully until we can't add any more characters without breaking the rules.
By always prioritizing the most abundant character while respecting the 'no three in a row' rule, we naturally build the longest possible happy string.

Code Implementation

import heapq

def longestDiverseString(a, b, c):
    result_list = []
    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'))

    while max_heap:
        count, character = heapq.heappop(max_heap)

        # If adding this character would create three in a row, we must use a different one.

        if len(result_list) >= 2 and result_list[-1] == character and result_list[-2] == character:
            # If no other characters are available, we must stop to avoid breaking the rule.

            if not max_heap:
                break

            second_count, second_character = heapq.heappop(max_heap)
            result_list.append(second_character)
            second_count += 1
            if second_count < 0:
                heapq.heappush(max_heap, (second_count, second_character))

            heapq.heappush(max_heap, (count, character)) # Put the original most frequent back.

        else:
            result_list.append(character)
            count += 1
            if count < 0:
                heapq.heappush(max_heap, (count, character))

    return "".join(result_list)

Big(O) Analysis

Time Complexity

O(a + b + c) – The total number of characters we can place is the sum of the initial counts, let's call this N = a + b + c. The core of the algorithm is a loop that continues as long as we can add characters to our result string. In each iteration of this loop, we perform a constant number of operations: comparing the three character counts to find the max and second max, and then appending one or two characters to the result. Since we add at least one character in every step, the loop will run at most N times. Therefore, the total time complexity is directly proportional to the total number of characters, which simplifies to O(a + b + c).

Space Complexity

O(A + B + C) – The primary space consumption comes from storing the result string itself. In the worst-case scenario, all available characters 'a', 'b', and 'c' can be used to form the final happy string. Therefore, the space required for the result string grows linearly with the total number of input characters, which is the sum of the initial counts A, B, and C. The variables used to track the remaining counts of each character consume a constant amount of space, which is negligible in comparison.

Edge Cases

Case	How to Handle
All counts are zero (a=0, b=0, c=0)	The algorithm should correctly produce an empty string as no characters are available to use.
One or two of the counts are zero (e.g., a=5, b=0, c=0)	The solution should build a string of length 2 (e.g., "aa") and then stop, as no other characters are available to break the consecutive sequence.
Highly skewed distribution of counts (e.g., a=100, b=1, c=1)	The greedy approach must be able to handle this by using the rare characters to break up long sequences of the most frequent character (e.g., "aabaacaa...").
All counts are equal (e.g., a=3, b=3, c=3)	The algorithm should alternate between the characters to produce a balanced string like "aabbaacc..." or "abcabc...".
One count is much larger than the sum of the other two (e.g., a=7, b=1, c=1)	The solution should use at most two of the dominant character, followed by one of the others, until the less frequent ones are exhausted (e.g., "aabaacaa").
Inputs are the minimum possible non-zero values (e.g., a=1, b=1, c=0)	The solution should correctly form a simple valid string like "ab" or "ba" by using the available characters.
Input counts are very large, nearing language-specific integer limits	The solution should use data types that can handle large numbers, and the iterative string-building process must be memory-efficient.
The problem constraints guarantee non-negative inputs (a, b, c >= 0)	The solution does not need to handle negative inputs, but it should be robust enough to work with zero counts as specified.

All counts are zero (a=0, b=0, c=0)

How to Handle:

The algorithm should correctly produce an empty string as no characters are available to use.

One or two of the counts are zero (e.g., a=5, b=0, c=0)

How to Handle:

The solution should build a string of length 2 (e.g., "aa") and then stop, as no other characters are available to break the consecutive sequence.

Highly skewed distribution of counts (e.g., a=100, b=1, c=1)

How to Handle:

The greedy approach must be able to handle this by using the rare characters to break up long sequences of the most frequent character (e.g., "aabaacaa...").

All counts are equal (e.g., a=3, b=3, c=3)

How to Handle:

The algorithm should alternate between the characters to produce a balanced string like "aabbaacc..." or "abcabc...".

One count is much larger than the sum of the other two (e.g., a=7, b=1, c=1)

How to Handle:

The solution should use at most two of the dominant character, followed by one of the others, until the less frequent ones are exhausted (e.g., "aabaacaa").

Inputs are the minimum possible non-zero values (e.g., a=1, b=1, c=0)

How to Handle:

The solution should correctly form a simple valid string like "ab" or "ba" by using the available characters.

Input counts are very large, nearing language-specific integer limits

How to Handle:

The solution should use data types that can handle large numbers, and the iterative string-building process must be memory-efficient.

The problem constraints guarantee non-negative inputs (a, b, c >= 0)

How to Handle:

The solution does not need to handle negative inputs, but it should be robust enough to work with zero counts as specified.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the input integers a, b, and c? Can they be zero, and what is their maximum possible value?
Is it possible for the input to be such that no non-empty happy string can be formed, for example, if two of the counts are zero? If so, what should be returned?
The problem asks for 'the' longest happy string. If there are multiple strings of the same maximum length, is any one of them acceptable?
Just to be certain about the definition of 'happy', does the rule against three consecutive characters apply only to 'aaa', 'bbb', and 'ccc', or could there be other characters involved in a more general version of this problem?
If one character count is significantly larger than the sum of the other two, for instance, a = 100, b = 1, c = 1, will there be a case where we can't use all the characters?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, imagine all the letters 'a', 'b', and 'c' we have available.
Start building a string by picking one letter at a time.
At each step of building the string, we have a choice of which letter to add next from the ones we still have left.
We need to explore every single path of choices. For example, after picking 'a', we could then pick another 'a', or a 'b', or a 'c'.
We continue this process of adding one letter at a time, trying every possible sequence, until we have used up all the letters.
This creates a massive list of every possible arrangement of the given letters.
Now, go through this entire list of generated strings one by one.
For each string, check if it's 'happy' – meaning, it doesn't have 'aaa', 'bbb', or 'ccc' anywhere inside it.
Keep track of all the strings that pass this check.
Finally, from the collection of all 'happy' strings, find the longest one and that's our answer.

Code Implementation

def longestHappyString(a_count: int, b_count: int, c_count: int) -> str:
    all_possible_happy_strings = []

    def generate_strings(current_string, remaining_a, remaining_b, remaining_c):
        # A string is a candidate for the final list once we've exhausted one or more characters.
        if len(current_string) > 1:
            all_possible_happy_strings.append(current_string)

        # Explore adding 'a' if it's available and doesn't create 'aaa'.
        if remaining_a > 0 and not current_string.endswith('aa'):
            generate_strings(current_string + 'a', remaining_a - 1, remaining_b, remaining_c)

        # Explore adding 'b' if it's available and doesn't create 'bbb'.
        if remaining_b > 0 and not current_string.endswith('bb'):
            generate_strings(current_string + 'b', remaining_a, remaining_b - 1, remaining_c)

        # Explore adding 'c' if it's available and doesn't create 'ccc'.
        if remaining_c > 0 and not current_string.endswith('cc'):
            generate_strings(current_string + 'c', remaining_a, remaining_b, remaining_c - 1)

    generate_strings("", a_count, b_count, c_count)

    longest_string_found = ""
    for candidate_string in all_possible_happy_strings:
        if len(candidate_string) > len(longest_string_found):
            longest_string_found = candidate_string

    # After checking all generated happy strings, return the one with the maximum length.
    return longest_string_found

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, figure out which character ('a', 'b', or 'c') you have the most of.
Try to add two of that most frequent character to our result string. This is the fastest way to use up characters.
Before adding them, check if the last two characters of our result string are already the same as the one we're about to add. If they are, we can't add this character right now.
If we can't add the most common character, look at the second-most common character and try to add just one of that to our string instead.
After adding a character (or two), update the remaining counts for 'a', 'b', and 'c'.
Repeat this process of picking the most frequent available character and adding it carefully until we can't add any more characters without breaking the rules.
By always prioritizing the most abundant character while respecting the 'no three in a row' rule, we naturally build the longest possible happy string.

Code Implementation

import heapq

def longestDiverseString(a, b, c):
    result_list = []
    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'))

    while max_heap:
        count, character = heapq.heappop(max_heap)

        # If adding this character would create three in a row, we must use a different one.

        if len(result_list) >= 2 and result_list[-1] == character and result_list[-2] == character:
            # If no other characters are available, we must stop to avoid breaking the rule.

            if not max_heap:
                break

            second_count, second_character = heapq.heappop(max_heap)
            result_list.append(second_character)
            second_count += 1
            if second_count < 0:
                heapq.heappush(max_heap, (second_count, second_character))

            heapq.heappush(max_heap, (count, character)) # Put the original most frequent back.

        else:
            result_list.append(character)
            count += 1
            if count < 0:
                heapq.heappush(max_heap, (count, character))

    return "".join(result_list)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
All counts are zero (a=0, b=0, c=0)	The algorithm should correctly produce an empty string as no characters are available to use.
One or two of the counts are zero (e.g., a=5, b=0, c=0)	The solution should build a string of length 2 (e.g., "aa") and then stop, as no other characters are available to break the consecutive sequence.
Highly skewed distribution of counts (e.g., a=100, b=1, c=1)	The greedy approach must be able to handle this by using the rare characters to break up long sequences of the most frequent character (e.g., "aabaacaa...").
All counts are equal (e.g., a=3, b=3, c=3)	The algorithm should alternate between the characters to produce a balanced string like "aabbaacc..." or "abcabc...".
One count is much larger than the sum of the other two (e.g., a=7, b=1, c=1)	The solution should use at most two of the dominant character, followed by one of the others, until the less frequent ones are exhausted (e.g., "aabaacaa").
Inputs are the minimum possible non-zero values (e.g., a=1, b=1, c=0)	The solution should correctly form a simple valid string like "ab" or "ba" by using the available characters.
Input counts are very large, nearing language-specific integer limits	The solution should use data types that can handle large numbers, and the iterative string-building process must be memory-efficient.
The problem constraints guarantee non-negative inputs (a, b, c >= 0)	The solution does not need to handle negative inputs, but it should be robust enough to work with zero counts as specified.

All counts are zero (a=0, b=0, c=0)

How to Handle:

The algorithm should correctly produce an empty string as no characters are available to use.

One or two of the counts are zero (e.g., a=5, b=0, c=0)

How to Handle:

The solution should build a string of length 2 (e.g., "aa") and then stop, as no other characters are available to break the consecutive sequence.

Highly skewed distribution of counts (e.g., a=100, b=1, c=1)

How to Handle:

The greedy approach must be able to handle this by using the rare characters to break up long sequences of the most frequent character (e.g., "aabaacaa...").

All counts are equal (e.g., a=3, b=3, c=3)

How to Handle:

The algorithm should alternate between the characters to produce a balanced string like "aabbaacc..." or "abcabc...".

One count is much larger than the sum of the other two (e.g., a=7, b=1, c=1)

How to Handle:

The solution should use at most two of the dominant character, followed by one of the others, until the less frequent ones are exhausted (e.g., "aabaacaa").

Inputs are the minimum possible non-zero values (e.g., a=1, b=1, c=0)

How to Handle:

The solution should correctly form a simple valid string like "ab" or "ba" by using the available characters.

Input counts are very large, nearing language-specific integer limits

How to Handle:

The solution should use data types that can handle large numbers, and the iterative string-building process must be memory-efficient.

The problem constraints guarantee non-negative inputs (a, b, c >= 0)

How to Handle:

The solution does not need to handle negative inputs, but it should be robust enough to work with zero counts as specified.

0/0 Capgemini questions completed

0/0 completed