Count the Unique AB Strings by Permutation

You are given a string s of “a” and “b”s. “a”s can stay “a” or turn into “b”, but “b”s can’t change.

Return the number of unique strings that can be made.

Constraints
1 ≤ n ≤ 10,000 where n is the length of s
Example 1
Input
s = “abba”
Output
4
Explanation
We can make these strings:

“abba”
“abbb”
“bbba”
“bbbb”

Number of Permutations

We can only turn a into b, and there will be two permutations for each a. Therefore, we have to count the number of a’s in the original string, and the answer is Pow(2, n):

C++ Code:

int uniquePermutationsOfABString(string s) {
    int a = 0;
    for (auto &n: s) {
        if (n == 'a') a ++;
    }
    return pow(2, a);
}

And Python:

class Solution:
    def solve(self, s):
        a = sum([1 for x in s if x == 'a'])
        return 2**a

Time complexity O(N) if we don’t consider the time spent on computing the Power function. THe space complexity is O(1).

–EOF (The Ultimate Computing & Technology Blog) —