Watch 7 video solutions for Maximize Number of Subsequences in a String, a medium level problem involving String, Greedy, Prefix Sum. This walkthrough by Bro Coders has 2,082 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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: 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".
Constraints:
1 <= text.length <= 105pattern.length == 2text and pattern consist only of lowercase English letters.Problem Overview: You are given a string text and a 2‑character string pattern. You may insert exactly one character (either pattern[0] or pattern[1]) anywhere in text. The goal is to maximize how many subsequences equal to pattern appear in the final string.
Approach 1: Counting Technique (Greedy) (Time: O(n), Space: O(1))
The optimal observation: a subsequence pattern[0]pattern[1] forms whenever a pattern[0] appears before a pattern[1]. Traverse the string once while counting how many pattern[0] characters have appeared so far. Every time you see pattern[1], add the current count of pattern[0] to the total subsequences. This gives the number of existing subsequences. To maximize the result, you decide where to insert the extra character: inserting pattern[0] at the beginning pairs with every existing pattern[1], while inserting pattern[1] at the end pairs with every existing pattern[0]. Choose the larger of those two counts and add it to the base subsequence count. This greedy counting method scans the string once, uses constant memory, and handles edge cases like pattern[0] == pattern[1] by simple combination counting.
Approach 2: Simulation with Detailed Insertion Check (Time: O(n), Space: O(n))
This approach explicitly simulates the effect of inserting characters at strategic positions. Precompute prefix counts of pattern[0] and suffix counts of pattern[1] using arrays similar to a prefix sum technique. Then evaluate the total subsequences formed if you insert pattern[0] at the beginning or pattern[1] at the end by combining these prefix and suffix counts. While less elegant than the greedy counting method, it makes the mechanics of subsequence formation very clear and is useful when reasoning about more complex variants. The extra arrays increase memory usage but keep the runtime linear.
Both approaches rely on sequential scanning of characters, which is common in string problems. The final decision—where to insert the character—is a classic greedy choice because only the global counts of the two pattern characters matter.
Recommended for interviews: The Counting Technique is what interviewers typically expect. It shows you understand how subsequences accumulate during a single pass and how a greedy insertion decision maximizes the final count. Mentioning the simulation idea first can demonstrate reasoning, but implementing the O(n) greedy solution shows strong algorithmic intuition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting Technique (Greedy) | O(n) | O(1) | Best general solution; single pass counting of pattern characters |
| Simulation with Prefix/Suffix Counts | O(n) | O(n) | Useful for understanding subsequence contributions or extending to more complex variants |