DP Solution for Number of subsequences of the form a^i b^j c^k

sohesh doshi
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))

--

--