#2207
Maximize Number of Subsequences in a String
expert · 1060 · lc medium +32 · verified · 36% accepted · 531 likes · top 14%
Description
You are given a 0-indexed string text and a 0-indexed string pattern of length 2, both consisting only of lowercase English letters.
You may insert either pattern[0] or pattern[1] at any position in text exactly once (including the beginning or end).
Return the maximum number of times pattern can appear as a subsequence in the modified text.
A subsequence is derived by deleting zero or more characters without changing the remaining order.
Example 1:
Input: text = "abdcdbc", pattern = "ac"
Output: 4
Explanation:
If we add pattern[0] = 'a' in between text[1] and text[2], we get "abadcdbc". Now, the number of times "ac" occurs as a subsequence is 4.
Some other strings which have 4 subsequences "ac" after adding a character to text are "aabdcdbc" and "abdacdbc".
However, strings such as "abdcadbc", "abdccdbc", and "abdcdbcc", although obtainable, have only 3 subsequences "ac" and are thus suboptimal.
It can be shown that it is not possible to get more than 4 subsequences "ac" by adding only one character.
Example 2:
Input: text = "aabb", pattern = "ab"
Output: 6
Explanation:
Some of the strings which can be obtained from text and have 6 subsequences "ab" are "aaabb", "aaabb", and "aabbb".
Code
1
2
3