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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.