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.

• Java
• C++
• Python
• Go

• 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