have 6 subsequences "ab" are "_**a**_ aabb", "aa _**a**_ bb", and "aab _**b**_ b".

Constraints

1 <= text.length <= 10^5
pattern.length == 2
text and pattern consist only of lowercase English letters.

Solution

Method 1 – Greedy Counting and Insertion

Intuition

To maximize the number of subsequences equal to pattern, we can insert either pattern[0] or pattern[1] anywhere in the string. The best strategy is to insert the character that increases the count the most. We count the number of subsequences for both options and return the maximum.

Approach

Count the number of pattern[0] and pattern[1] in text.
Count the num

Related Tags