Statement
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, and
The substring 'bbb' does not occur in s.
Input
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"
Constraints
0 <= a, b <= 100
It is guaranteed such an s exists for the given a and b.
Approach :
There are generally 4 conditions that may occur.
- a < 3 && b < 3
For this we simply print the string in any way we want as we will not get aaa
or bbb
as substring.
- a >= 3 && b < 3
For this, we put b
whenever the last 2 characters are aa
as there may be a substring aaa
.
- a < 3 && b >= 3
For this, we put a
whenever the last 2 characters are bb
as there may be a substring bbb
.
- a >= 3 && b >= 3
For this, whenever we see aa
as the last 2 characters, start printing b
and whenever we see bb
as the last 2 characters, start print a
.
This is the basic idea we can use to solve this problem and in Java there is endsWith()
method which is very much handy in this case. We can use it like endsWith("aa")
or endsWith("bb")
in checking for the conditions.
Code
class Solution {
public String strWithout3a3b(int a, int b) {
StringBuilder sb = new StringBuilder();
while (a > 0 || b > 0) {
String s = sb.toString();
// if we have aa as the last 2 characters, then the next one is b
if (s.endsWith("aa")) {
sb.append("b");
b --;
}
// if we have bb as the last 2 characters, then the next one is a
else if (s.endsWith("bb")) {
sb.append("a");
a --;
}
// if a > b, append a
else if (a > b) {
sb.append("a");
a --;
}
// if b >= a, append b
else {
sb.append("b");
b --;
}
}
return sb.toString();
}
}
Complexity
Time Complexity : It will O(a + b) which is the length of the string
Space Complexity : It will be O(a + b) as we create a new string of length a + b and if we consider this into space analysis.
Github Links :
Leetcode Daily Challenges and Other platforms problems solved
Top comments (0)