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.
In this approach, we count the occurrences of the second character of the pattern as we traverse the text. For each character in the text, keep track of how many times the second character of the pattern can be combined with previous occurrences of the first character. We then calculate how inserting either pattern[0] or pattern[1] at each position affects this count, ultimately aiming to maximize the total number of subsequences formed.
The C code counts the number of 'second' pattern characters that can match with preceding 'first' pattern characters, simulating a subsequence. It then considers the effect of inserting either character into the string to maximize this count.
Time complexity is O(n), where n is the length of the text; Space complexity is O(1), as no additional data structures are used besides counters.
This approach involves simulating the addition of either the first or second character of the pattern at each possible position in the text, calculating the resultant subsequences possible following each potential insertion. By iterating through possible positions, it directly evaluates the greatest possible increase in subsequences due to each insertion scenario.
The C code explicitly constructs new strings with potential inserts of the pattern characters at every possible position, to count and evaluate potential max subsequences.
Time complexity is O(n2), as it checks each possible insertion position; Space complexity is O(n) for the modified string.
We can use two variables x and y to record the current counts of pattern[0] and pattern[1] in the string, respectively.
Then, traverse the string text. For the current character c:
c equals pattern[1], increment y by one. At this point, all previously encountered pattern[0] can form a pattern subsequence with the current c, so add x to the answer.c equals pattern[0], increment x by one.After the traversal, since we can insert one character, if we add pattern[0] at the beginning of the string, we can get y pattern subsequences. If we add pattern[1] at the end of the string, we can get x pattern subsequences. Therefore, we add the larger value of x and y to the answer.
The time complexity is O(n), where n is the length of the string text. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Counting Technique | Time complexity is O(n), where n is the length of the text; Space complexity is O(1), as no additional data structures are used besides counters. |
| Approach 2: Simulation with Detailed Insertion Check | Time complexity is O(n2), as it checks each possible insertion position; Space complexity is O(n) for the modified string. |
| Traversal + Counting | — |
| 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 |
2207. Maximize Number of Subsequences in a String || Biweekly Contest 74 || Leetcode 2207 • Bro Coders • 2,082 views views
Watch 6 more video solutions →Practice Maximize Number of Subsequences in a String with our built-in code editor and test cases.
Practice on FleetCode