DP Solution for Number of subsequences of the form a^i b^j c^k
1 min readJan 4, 2020
Number of subsequences of the form a^i b^j c^k
Given a string, count number of subsequences of the form a^ib^jc^k, i.e., it consists of i ’a’ characters, followed by j ’b’ characters, followed by k ’c’ characters where i >= 1, j >=1 and k >= 1.
from collections import Counterdef solution(totalcount): temp_ar=[0 for i in range(totalcount+1)] temp_ar[3]=1 for i in range(4,totalcount+1): temp_ar[i]=temp_ar[i-1]*3 return temp_ar[totalcount]def get_totalcount(str_ar): return solution(sum(Counter(str_ar).values()))str="abbcc"
print(get_totalcount(str))