78 lines
2.0 KiB
C++
78 lines
2.0 KiB
C++
// Source : https://leetcode.com/problems/string-without-aaa-or-bbb/
|
|
// Author : Hao Chen
|
|
// Date : 2019-01-29
|
|
|
|
/*****************************************************************************************************
|
|
*
|
|
* Given two integers A and B, return any string S such that:
|
|
*
|
|
* S has length A + B and contains exactly A 'a' letters, and exactly B 'b' letters;
|
|
* The substring 'aaa' does not occur in S;
|
|
* The substring 'bbb' does not occur in S.
|
|
*
|
|
* Example 1:
|
|
*
|
|
* Input: A = 1, B = 2
|
|
* Output: "abb"
|
|
* Explanation: "abb", "bab" and "bba" are all correct answers.
|
|
*
|
|
* Example 2:
|
|
*
|
|
* Input: A = 4, B = 1
|
|
* Output: "aabaa"
|
|
*
|
|
* Note:
|
|
*
|
|
* 0 <= A <= 100
|
|
* 0 <= B <= 100
|
|
* It is guaranteed such an S exists for the given A and B.
|
|
******************************************************************************************************/
|
|
|
|
class Solution {
|
|
public:
|
|
string strWithout3a3b(int A, int B) {
|
|
|
|
string result;
|
|
while (true){
|
|
|
|
// if A == B, then just simpley repeat "ab" pattern;
|
|
if (A == B) {
|
|
for ( int i=0; i<A; i++ ) {
|
|
result += "ab";
|
|
}
|
|
break;
|
|
}
|
|
|
|
// if A+B less then 3 and A != B, which means A=1,2 && B=0 or A=0 && B=1,2
|
|
if (A+B <3) {
|
|
while ( A-- > 0 ) result += 'a';
|
|
while ( B-- > 0 ) result += 'b';
|
|
break;
|
|
}
|
|
|
|
// if A+B >=3 and A !=B
|
|
|
|
// if A > B, then we need consume 'a' more than 'b'
|
|
// So, only "aab" can be used.
|
|
if ( A > B ) {
|
|
result += "aab";
|
|
A -= 2;
|
|
B--;
|
|
continue;
|
|
}
|
|
|
|
// if A > B, then we need consume 'b' more than 'a'
|
|
// So, only "bba" can be used.
|
|
if (B > A ){
|
|
result += "bba";
|
|
B-=2;
|
|
A--;
|
|
continue;
|
|
}
|
|
|
|
}
|
|
|
|
return result;
|
|
}
|
|
};
|