abc | Practice Problems

abc

★★★★★

0 votes

Details

Problem

Those who cannot remember the past are condemned to repeat it.

-Dynamic Programming

Perfect Subsequence

A subsequence is called as Perfect Subsequence if it starts with atleast one a and followed by atleast on b and followed by atleast one c.

i.e the subsequence should be in form of aⁱ b^j c^k where $i>=1$ , $j>=1$ , $k>=1$

Now you will be given a string contains only a,b,c and you have to find number of Perfect Subsequences in it.

NOTE : Output might be large for some testcases so print answer Modulo $10^9 +7$

Input contains a string containing only a,b,c

Print number of perfect subsequences for given string

$1<=|S|<=100000$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

All Perfect Subsequences for given input are

abc -{1,2,3}

abc -{1,2,6}

abc -{1,5,6}

abc -{4,5,6}

abbc -{1,2,5,6}

aabc -{1,4,5,6}

abcc -{1,2,3,6}