LeetCode 984 - String Without AAA or BBB

https://leetcode.com/problems/string-without-aaa-or-bbb/

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

X. Greedy
https://leetcode.com/problems/string-without-aaa-or-bbb/discuss/226649/JavaC%2B%2B-(and-Python)-simple-greedy

• If the initial number of As is greater than Bs, we swap A and B.
• For each turn, we add 'a' to our string.
• If the number of remaining As is greater than Bs, we add one more 'a'.
• Finally, we add 'b'.

  public String strWithout3a3b(int A, int B) {

    StringBuilder res = new StringBuilder(A + B);

    char a = 'a', b = 'b';

    int i = A, j = B;

    if (B > A) {

      a = 'b';

      b = 'a';

      i = B;

      j = A;

    }

    while (i-- > 0) {

      res.append(a);

      if (i > j) {

        res.append(a);

        --i;

      }

      if (j-- > 0)

        res.append(b);

    }

    return res.toString();

  }

https://leetcode.com/articles/string-without-aaa-or-bbb/

Intuitively, we should write the most common letter first. For example, if we have A = 6, B = 2, we want to write 'aabaabaa'. The only time we don't write the most common letter is if the last two letters we have written are also the most common letter

Algorithm

Let's maintain A, B: the number of 'a' and 'b''s left to write.

If we have already written the most common letter twice, we'll write the other letter. Otherwise, we'll write the most common letter.

  public String strWithout3a3b(int A, int B) {

    StringBuilder ans = new StringBuilder();

    while (A > 0 || B > 0) {

      boolean writeA = false;

      int L = ans.length();

      if (L >= 2 && ans.charAt(L - 1) == ans.charAt(L - 2)) {

        if (ans.charAt(L - 1) == 'b')

          writeA = true;

      } else {

        if (A >= B)

          writeA = true;

      }

      if (writeA) {

        A--;

        ans.append('a');

      } else {

        B--;

        ans.append('b');

      }

    }

    return ans.toString();

  }

https://leetcode.com/problems/string-without-aaa-or-bbb/discuss/226720/Java-Two-simple-logic-readable-codes-iterative-and-recursive-versions.

1. If current result ends with aa, next char is b; if ends with bb, next char must be a.
2. Other cases, if A > B, next char is a; otherwise, next char is b.

    public String strWithout3a3b(int A, int B) {
        StringBuilder sb = new StringBuilder(A + B);
        while (A + B > 0) {
            String s = sb.toString();
            if (s.endsWith("aa")) {
                sb.append("b");
                --B;       
            }else if (s.endsWith("bb")){
                sb.append("a");
                --A;
            }else if (A > B) {
                sb.append("a");
                --A;
            }else {
                sb.append("b");
                --B;
            }
        }
        return sb.toString();
    }

Recursive Version, inspired by @lbjlc

    public String strWithout3a3b(int A, int B) {
        if (A == 0 || B == 0) { // if A or B is 0, return A 'a's or B 'b's.
            String s = "";
            for (int i = 0; i < A + B; ++i) { s += (A == 0 ? 'b' : 'a'); }
            return s;
        }
        if (A == B) { return "ab" + strWithout3a3b(A - 1, B - 1); }
        if (A > B) { return "aab" + strWithout3a3b(A - 2, B - 1); }
        return "bba" + strWithout3a3b(A - 1, B - 2);
    }

The base case in above recursive version can be rewritten as follows:

        if (A == 0 || B == 0) { // if A or B is 0, return A 'a's or B 'b's.
            String s = (A == 0 ? "b" : "a"); 
            return String.join("", Collections.nCopies(A + B, s)); 
        } 

X. Recursive
https://leetcode.com/problems/string-without-aaa-or-bbb/discuss/226740/Clean-C%2B%2Bpython-solution

    string strWithout3a3b(int A, int B) {
        if(A == 0) return string(B, 'b');
        else if(B == 0) return string(A, 'a');
        else if(A == B) return "ab" + strWithout3a3b(A - 1, B - 1);
        else if(A > B) return "aab" + strWithout3a3b(A - 2, B - 1);
        else return strWithout3a3b(A - 1, B - 2) + "abb";
    }