LeetCode-1405. Longest happy string

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

analysis ：

Adopt a greedy strategy , Select the longest character each time （max(a, b, c)） As a continuum , Then take less as the middle partition .

This ensures that the happy string is the longest .

#include<iostream>
#include<unordered_map>
using namespace std;
class Solution {
public:
	string longestDiverseString(int a, int b, int c) {
		string str;
		char ch;
		unordered_map<char, int> mp;
		mp['a'] = a;
		mp['b'] = b;
		mp['c'] = c;

		ch = maxch(mp['a'], mp['b'], mp['c']);
		while (mp[ch] != 0) {
			construct(mp[ch], ch, str);
			if (maxch(mp['a'], mp['b'], mp['c']) == ch) {
				if (savech(ch, mp['a'], mp['b'], mp['c'], str)) {
					ch = maxch(mp['a'], mp['b'], mp['c']);
					continue;
				}
				else {
					break;
				}
			}
			else {
				ch = maxch(mp['a'], mp['b'], mp['c']);
			}
		}


		return str;
	}

	bool savech(char ch, int& a, int& b, int& c, string& str) {
		bool issucc = true;
		if (ch != 'a' && a > 0) {
			str += 'a';
			a--;
		}
		else if (ch != 'b' && b > 0) {
			str += 'b';
			b--;
		}
		else if (ch != 'c' && c > 0) {
			str += 'c';
			c--;
		}
		else {
			issucc = false;
		}
		return issucc;
	}

	char maxch(int a, int b, int c) {
		if (a >= b) {
			if (a >= c) {
				return 'a';
			}
			else {
				return 'c';
			}
		}
		else if (c >= b) {
			return 'c';
		}
		else {
			return 'b';
		}
	}


	void construct(int& num, char c, string& str) {
		if (num >= 2) {
			num = num - 2;
			str += c;
			str += c;
		}
		else if (num == 1) {
			num = num - 1;
			str += c;
		}
	}

};


int main() {
	Solution* ps = new Solution();
	unique_ptr<Solution> ptr(new Solution());
	cout << ps->longestDiverseString(7, 1, 0) << endl;
	system("pause");
	return 0;
}