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:
1 2 3 4 5 6 7 | int uniquePermutationsOfABString(string s) { int a = 0; for (auto &n: s) { if (n == 'a') a ++; } return pow(2, a); } |
int uniquePermutationsOfABString(string s) {
int a = 0;
for (auto &n: s) {
if (n == 'a') a ++;
}
return pow(2, a);
}And Python:
1 2 3 4 | class Solution: def solve(self, s): a = sum([1 for x in s if x == 'a']) return 2**a |
class Solution:
def solve(self, s):
a = sum([1 for x in s if x == 'a'])
return 2**aTime 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) —
GD Star Rating
loading...
255 wordsloading...
Last Post: Teaching Kids Programming - Using Binary Search to Find K-th Largest Number in Array
Next Post: Python's zip_longest Function
