Skip to content

Latest commit

 

History

History
63 lines (49 loc) · 1.92 KB

README.md

File metadata and controls

63 lines (49 loc) · 1.92 KB

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:

  1. 0 <= A <= 100
  2. 0 <= B <= 100
  3. It is guaranteed such an S exists for the given A and B.

Related Topics:
Greedy

Solution 1.

// OJ: https://leetcode.com/problems/string-without-aaa-or-bbb/
// Author: github.com/lzl124631x
// Time: O(A + B)
// Space: O(1)
class Solution {
public:
    string strWithout3a3b(int A, int B) {
        char a = 'a', b = 'b';
        if (A < B) swap(A, B), swap(a, b);
        string ans;
        while (A && B) {
            for (int i = A > B ? 2 : 1; i > 0; --i, --A) ans += a;
            ans += b;
            --B;
        }
        while (A-- > 0) ans += a;
        return ans;
    }
};