Maximize Number of Subsequences in a String

Problem Description

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. Return the maximum number of times pattern can occur as a subsequence of the modified text.

Key Insights

• A subsequence can be formed by deleting characters without changing the order of the remaining characters.
• We can enhance the number of occurrences of the pattern by strategically adding one of the characters to the text.
• The ability to add a character at any position allows us to maximize subsequences by increasing the count of necessary characters in the right order.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can approach it in the following steps:

1. Count the occurrences of both characters in the pattern within the original text.
2. For each character in the pattern, simulate the addition of that character to the text.
3. Calculate the new number of subsequences formed by this addition.
4. Return the maximum count obtained from the two simulations.

We'll use a two-pointer technique to count subsequences efficiently, keeping track of the counts of pattern[0] and pattern[1] as we iterate through the text.

Code Solutions