Leetcode 984. String Without AAA or BBB

Problem Explanation

We have been given two integers A and B. We need to return a string S that has a length of A + B and contains exactly A 'a' letters, and exactly B 'b' letters. However, there are a few conditions, the substring 'aaa' or 'bbb' must not occur in S.

For instance,

• Given A = 1 and B = 2, Output can be "abb" or "bba"

• Given A = 4 and B = 1, Output can be "aabaa"

Approach

The approach to solve this problem is to always add more of 'a' or 'b' (depending on which count is more) and then "a" or "b", alternating between both until either A or B is exhausted. Once either of 'a' or 'b' is exhausted, add the remaining of the other letter to the string but not more than two at a time to avoid the string 'aaa' or 'bbb'

Python Solution

Here is the Python solution.

1
2Python
3class Solution:
4  def strWithout3a3b(self, A: int, B: int, a: str = 'a', b: str = 'b') -> str:
5    # if A < B, swap A and B with a and b
6    if A < B:
7      return self.strWithout3a3b(B, A, b, a)
8    # if no b's left, return a's not more than twice in a row
9    if B == 0:
10      return min(A, 2)*a
11
12    # decide how many a's and b's to use
13    use_a = min(2, A)
14    use_b = 1 if A - use_a >= B else 0
15    return use_a*a + use_b*b + self.strWithout3a3b(A - use_a, B - use_b, a, b)

Java Solution

Here is the Java solution.

1
2Java
3class Solution {
4  public String strWithout3a3b(int A, int B, char a = 'a', char b = 'b') {
5    // if A < B, swap A and B with a and b
6    if (A < B)
7      return strWithout3a3b(B, A, b, a);
8    
9    // if no b's left, return a's not more than twice in a row
10    if (B == 0)
11      return String.valueOf(a).repeat(Math.min(A, 2));
12
13    // decide how many a's and b's to use
14    int use_a = Math.min(A, 2);
15    int use_b = (A - use_a >= B) ? 1 : 0;
16    return String.valueOf(a).repeat(use_a) + 
17           String.valueOf(b).repeat(use_b) + 
18           strWithout3a3b(A - use_a, B - use_b, a, b);
19  }
20}

C++ Solution

Here is the C++ solution.

1
2C++
3class Solution {
4public:
5  string strWithout3a3b(int A, int B, char a = 'a', char b = 'b') {
6    // if A < B, swap A and B with a and b
7    if (A < B)
8      return strWithout3a3b(B, A, b, a);
9    
10    // if no b's left, return a's not more than twice in a row
11    if (B == 0)
12      return string(min(A, 2), a);
13
14    // decide how many a's and b's to use
15    int use_a = min(A, 2);
16    int use_b = (A - use_a >= B) ? 1 : 0;
17    return string(use_a, a)  + 
18           string(use_b, b)  +
19           strWithout3a3b(A - use_a, B - use_b, a, b);
20  }
21};

C# Solution

Here is the C# solution.

1
2Csharp
3public class Solution {
4  public string StrWithout3a3b(int A, int B, char a = 'a', char b = 'b') {
5    // if A < B, swap A and B with a and b
6    if (A < B)
7      return StrWithout3a3b(B, A, b, a);
8    
9    // if no b's left, return a's not more than twice in a row
10    if (B == 0)
11      return new string(a, Math.Min(A, 2));
12
13    // decide how many a's and b's to use
14    int use_a = Math.Min(A, 2);
15    int use_b = (A - use_a >= B) ? 1 : 0;
16    return new string(a, use_a) + 
17           new string(b, use_b) + 
18           StrWithout3a3b(A - use_a, B - use_b, a, b);
19  }
20}

Javascript Solution

Following the same concept of choosing which character to place next based on the number of 'a' and 'b' left and avoiding three consecutive same characters, we can solve the problem via JavaScript as well.

Here is the JavaScript solution.

1
2JavaScript
3var strWithout3a3b = function (A, B, a = 'a', b = 'b') {
4    // if A < B, swap A and B with a and b
5    if (A < B) {
6        return strWithout3a3b(B, A, b, a);
7    }
8
9    // if no b's left, return a's not more than twice in a row.
10    if (B === 0) {
11        return a.repeat(Math.min(A, 2));
12    }
13    
14   // decide how many a's and b's to use
15    var use_a = Math.min(A, 2);
16    var use_b = (A - use_a >= B) ? 1 : 0;
17    return a.repeat(use_a)  + 
18           b.repeat(use_b)  +
19           strWithout3a3b(A - use_a, B - use_b, a, b);
20};

In this JavaScript solution, we are using a recursive function, utilizing built-in repeat function for string manipulations. This function has the same logic as the Python, Java, C++ and C# solutions presented before.

It's important to note that the repeat function was used to replicate a character a given number of times, and Math.min was used to make sure we don't repeat a character more than twice consecutively, ensuring the condition to not have 'aaa' or 'bbb' in the result string is upheld.