Formatted question description: https://leetcode.ca/all/984.html

984. String Without AAA or BBB (Medium)

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/

// 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;
    }
};

Java

class Solution {
    public String strWithout3a3b(int A, int B) {
        StringBuffer sb = new StringBuffer();
        while (A > B && B > 0) {
            sb.append("aab");
            A -= 2;
            B--;
        }
        while (A < B && A > 0) {
            sb.append("bba");
            B -= 2;
            A--;
        }
        while (A > 0 && B > 0) {
            sb.append("ab");
            A--;
            B--;
        }
        while (A > 0) {
            sb.append("a");
            A--;
        }
        while (B > 0) {
            sb.append("b");
            B--;
        }
        return sb.toString();
    }
}

All Problems

All Solutions