Maximize Number of Subsequences in a String
You are given a 0-indexed string text and another 0-indexed string pattern of length 2, both of which consist of only lowercase English letters.
You can add either pattern[0] or pattern[1] anywhere in text exactly once. Note that the character can be added even at the beginning or at the end of text.
Return the maximum number of times pattern can occur as a subsequence of the modified text.
A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
Example 1
Input
text = "abdcdbc", pattern = "ac"Output
4Adding an
a in an optimal position can make pattern occur as a subsequence 4 times, and it is not possible to get more than 4.Example 2
Input
text = "aabb", pattern = "ab"Output
6Some modified strings such as
aaabb or aabbb contain 6 subsequences equal to ab.Constraints
- 1 <= text.length <= 10^5
- pattern.length == 2
- text and pattern consist only of lowercase English letters.
Asked at 1 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.