Description

1405. Longest Happy String

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

Answer & Explaining

#include <stdio.h>
#include <stdlib.h>

char* longestDiverseString(int a, int b, int c) {
    int total = a + b + c; //字母總數
    char* result = (char*)malloc(sizeof(char) * (total + 1)); //分配(total+1)的記憶體空間給result陣列。+1是給結束符
    int idx = 0; //初始化index，代表目前追蹤到的字串位置，來確認要在哪裡插入
    
    // 字母的數量與對應字母初始化
    int count[3] = {a, b, c}; //分別儲存a, b, c剩餘的數量的陣列
    char letters[3] = {'a', 'b', 'c'};//字元陣列，對應a, b, c
    
    while (total > 0) {
        // 找出數量最多與次多的字母
        int first = (count[0] >= count[1]) ? ((count[0] >= count[2]) ? 0 : 2) : ((count[1] >= count[2]) ? 1 : 2);
        int second = (count[0] >= count[1]) ? ((count[0] >= count[2]) ? ((count[1] >= count[2]) ? 1 : 2) : 0) : ((count[1] >= count[2]) ? ((count[0] >= count[2]) ? 0 : 2) : 1);

        // 如果字母已經連續出現兩次，則嘗試使用次多的字母
        if (idx >= 2 && result[idx - 1] == letters[first] && result[idx - 2] == letters[first]) {
            if (count[second] == 0) break;  // 次多字母用完則退出
            //將次多字母插入result
            result[idx++] = letters[second];
            count[second]--;
        } else {
            if (count[first] == 0) break;  // 最多字母用完則退出
            result[idx++] = letters[first];
            count[first]--;
        }
        total--;//每次結束total--
    }

    result[idx] = '\0';  // 結束符
    return result;
}

Testing

#include <stdio.h>
#include <stdlib.h>

char* longestDiverseString(int a, int b, int c) {
    int total = a + b + c; //字母總數
    char* result = (char*)malloc(sizeof(char) * (total + 1)); //分配(total+1)的記憶體空間給result陣列。+1是給結束符
    int idx = 0; //初始化index，代表目前追蹤到的字串位置，來確認要在哪裡插入
    
    // 字母的數量與對應字母初始化
    int count[3] = {a, b, c}; //分別儲存a, b, c剩餘的數量的陣列
    char letters[3] = {'a', 'b', 'c'};//字元陣列，對應a, b, c
    
    while (total > 0) {
        // 找出數量最多與次多的字母
        int first = (count[0] >= count[1]) ? ((count[0] >= count[2]) ? 0 : 2) : ((count[1] >= count[2]) ? 1 : 2);
        int second = (count[0] >= count[1]) ? ((count[0] >= count[2]) ? ((count[1] >= count[2]) ? 1 : 2) : 0) : ((count[1] >= count[2]) ? ((count[0] >= count[2]) ? 0 : 2) : 1);

        // 如果字母已經連續出現兩次，則嘗試使用次多的字母
        if (idx >= 2 && result[idx - 1] == letters[first] && result[idx - 2] == letters[first]) {
            if (count[second] == 0) break;  // 次多字母用完則退出
            //將次多字母插入result
            result[idx++] = letters[second];
            count[second]--;
        } else {
            if (count[first] == 0) break;  // 最多字母用完則退出
            result[idx++] = letters[first];
            count[first]--;
        }
        total--;//每次結束total--
    }

    result[idx] = '\0';  // 結束符
    return result;
}

int main() {
    int a = 1, b = 1, c = 7;
    char* result = longestDiverseString(a, b, c);
    printf("Test case 1: %s\n", result);  // Expected: ccaccbcc or similar
    free(result);
    return 0;
}