984 : String Without AAA or BBB - Leetcode Medium

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 :

Leetcodes Problems Solved

Leetcode Daily Challenges and Other platforms problems solved