Happy string

1405. The longest happy string

Medium difficulty

If the string does not contain any  'aaa','bbb'  or  'ccc'  Such a string is used as a substring , Then the string is a 「 Happy string 」.

Here are three integers  a,b ,c, Please return   Any one   A string that satisfies all of the following conditions  s：

• s  Is a happy string as long as possible .

• s  in   most   Yes a  Letters  'a'、b  Letters  'b'、c  Letters  'c' .

• s  It only contains  'a'、'b' 、'c'  Three letters .

If such a string does not exist  s , Please return an empty string  "".

Example 1：

Input ：a = 1, b = 1, c = 7 Output ："ccaccbcc" explain ："ccbccacc" It is also a correct answer .

Example 2：

Input ：a = 2, b = 2, c = 1 Output ："aabbc"

Example 3：

Input ：a = 7, b = 1, c = 0 Output ："aabaa" explain ： This is the only correct answer to the test case .

Tips ：

• 0 <= a, b, c <= 100
• a + b + c > 0

-*******

Method 1 ： greedy

Ideas

The title requires finding the longest happy string , And the happy string does not contain three consecutive identical letters . To find the longest string , We can use the following greedy strategies ：

Give priority to the current maximum number of letters as much as possible , Because the more letters of the same kind are left , The more likely it is to have the same letters in succession . If there are still unselected letters after the longest happy string is built , Then the remaining letters must be the same letter and the total number of this letter is the largest .

Start with the largest number of letters in turn , If it is found that adding the current letter will result in three consecutive identical letters , Skip the current letter , Until we find the letters we can add . In fact, only one of the largest and second largest letters will be selected at a time .

If you try all the letters, you can't add , You just quit , The string formed at this time is the longest happy string .

Java

class Solution {
    public String longestDiverseString(int a, int b, int c) {
        StringBuilder res = new StringBuilder();
        Pair[] arr = {new Pair(a, 'a'), new Pair(b, 'b'), new Pair(c, 'c')};
        
        while (true) {
            Arrays.sort(arr, (p1, p2) -> p2.freq - p1.freq);
            boolean hasNext = false;
            for (Pair pair : arr) {
                if (pair.freq <= 0) {
                    break;
                }
                int m = res.length();
                if (m >= 2 && res.charAt(m - 2) == pair.ch && res.charAt(m - 1) == pair.ch) {
                    continue;
                }
                hasNext = true;
                res.append(pair.ch);
                pair.freq--;
                break;
            }
            if (!hasNext) {
                break;
            }
        }
      
        return res.toString();
    }

    class Pair {
        int freq;
        char ch;

        public Pair(int freq, char ch) {
            this.freq = freq;
            this.ch = ch;
        }
    }
}

python

class Solution:
    def longestDiverseString(self, a: int, b: int, c: int) -> str:
        ans = []
        cnt = [[a, 'a'], [b, 'b'], [c, 'c']]
        while True:
            cnt.sort(key=lambda x: -x[0])
            hasNext = False
            for i, (c, ch) in enumerate(cnt):
                if c <= 0:
                    break
                if len(ans) >= 2 and ans[-2] == ch and ans[-1] == ch:
                    continue
                hasNext = True
                ans.append(ch)
                cnt[i][0] -= 1
                break
            if not hasNext:
                return ''.join(ans)