Welcome to Subscribe On Youtube

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.

  • 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();
        }
    }
    
    ############
    
    class Solution {
        public String strWithout3a3b(int a, int b) {
            StringBuilder ans = new StringBuilder();
            while (a > 0 && b > 0) {
                if (a > b) {
                    ans.append("aab");
                    a -= 2;
                    b -= 1;
                } else if (a < b) {
                    ans.append("bba");
                    a -= 1;
                    b -= 2;
                } else {
                    ans.append("ab");
                    --a;
                    --b;
                }
            }
            if (a > 0) {
                ans.append("a".repeat(a));
            }
            if (b > 0) {
                ans.append("b".repeat(b));
            }
            return ans.toString();
        }
    }
    
  • // 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;
        }
    };
    
  • class Solution:
        def strWithout3a3b(self, a: int, b: int) -> str:
            ans = []
            while a and b:
                if a > b:
                    ans.append('aab')
                    a, b = a - 2, b - 1
                elif a < b:
                    ans.append('bba')
                    a, b = a - 1, b - 2
                else:
                    ans.append('ab')
                    a, b = a - 1, b - 1
            if a:
                ans.append('a' * a)
            if b:
                ans.append('b' * b)
            return ''.join(ans)
    
    ############
    
    class Solution(object):
        def strWithout3a3b(self, A, B):
            """
            :type A: int
            :type B: int
            :rtype: str
            """
            _len = A + B
            # to make A > B
            a, b = ('a', 'b') if A > B else ('b', 'a')
            A, B = (A, B) if A > B else (B, A)
            ab = [a + b] * B
            A -= B
            res = []
            while A:
                res.append(a)
                if ab:
                    res.append(ab.pop())
                A -= 1
            res += ab
            return "".join(res)
    
  • func strWithout3a3b(a int, b int) string {
    	var ans strings.Builder
    	for a > 0 && b > 0 {
    		if a > b {
    			ans.WriteString("aab")
    			a -= 2
    			b -= 1
    		} else if a < b {
    			ans.WriteString("bba")
    			a -= 1
    			b -= 2
    		} else {
    			ans.WriteString("ab")
    			a--
    			b--
    		}
    	}
    	if a > 0 {
    		ans.WriteString(strings.Repeat("a", a))
    	}
    	if b > 0 {
    		ans.WriteString(strings.Repeat("b", b))
    	}
    	return ans.String()
    }
    

All Problems

All Solutions