Choose one character to insert into a string so that the number of subsequences equal to a given 2-character pattern is maximized.
Maximum Number of Subsequences After One Inserting
You are given a string text and a string pattern of length 2.
You may insert exactly one character, either pattern[0] or pattern[1], into any position of text (including the beginning or the end).
After the insertion, count how many subsequences of the resulting string are equal to pattern.
Return the maximum possible number of such subsequences.
A subsequence is formed by deleting zero or more characters without changing the order of the remaining characters.
Input Format
text: a stringpattern: a string of length 2
You may insert one character from pattern at any position in text.
Output Format
Return the maximum number of subsequences equal to pattern after one insertion.
Constraints
1 <= text.length <= $10^{5}$pattern.length == 2textandpatterncontain lowercase English letters- You must insert exactly one character
Example 1
Input
text = "abdcdbc", pattern = "ac"
Output
4
Explanation
Insert 'a' at the beginning or 'c' at the end to maximize the number of subsequences equal to "ac". The best choice yields 4 subsequences.
Example 2
Input
text = "aabb", pattern = "ab"
Output
6
Explanation
The original string already has 4 subsequences equal to "ab". Inserting another 'a' at the beginning or another 'b' at the end increases the count to 6.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.