Skip to main content
Talentd

Maximize Number of Subsequences in a String - Solution & Explanation

MediumStringGreedyPrefix Sum18 min readAsked at: Amazon
Practice this problem

Problem Statement

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 <= 105
  • pattern.length == 2
  • text and pattern consist only of lowercase English letters.

Approach Overview

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 1: Approach 1: Counting Technique

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Simulation with Detailed Insertion Check

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time complexity is O(n2), as it checks each possible insertion position; Space complexity is O(n) for the modified string.

Try this approach in the editor →

Approach 3: Traversal + Counting

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:

  • If 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.
  • If 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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Counting Technique (Greedy)O(n)O(1)Best general solution; single pass counting of pattern characters
Simulation with Prefix/Suffix CountsO(n)O(n)Useful for understanding subsequence contributions or extending to more complex variants

Video Solution

2207. Maximize Number of Subsequences in a String || Biweekly Contest 74 || Leetcode 2207 • Bro Coders • 2,103 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Maximize Number of Subsequences in a String easy or hard?
The problem is rated Medium because the implementation is simple but the greedy insight is not immediately obvious. Many candidates initially try brute force insertion checks before realizing the result depends only on the counts of the two pattern characters.
Maximize Number of Subsequences in a String Python/Java solution
In Python or Java, iterate through the string and maintain counters for pattern[0] and total subsequences. When pattern[1] appears, add the current pattern[0] count to the answer. Finally add max(countPattern0, countPattern1) to simulate the optimal insertion.
How to solve Maximize Number of Subsequences in a String in O(n)?
Scan the string while maintaining a counter for pattern[0]. Each time pattern[1] appears, add the current pattern[0] count to the subsequence total. After computing the base subsequences, add max(totalPattern0, totalPattern1) because inserting pattern[0] at the start pairs with all pattern[1] characters, while inserting pattern[1] at the end pairs with all pattern[0] characters.
What is the best approach for Maximize Number of Subsequences in a String?
The best approach is a greedy counting technique. Traverse the string once while counting occurrences of pattern[0], and add that count whenever pattern[1] appears to compute existing subsequences. Then add the maximum of total pattern[0] or pattern[1] occurrences depending on whether inserting pattern[1] at the end or pattern[0] at the beginning creates more subsequences. This runs in O(n) time and O(1) space.
Is Maximize Number of Subsequences in a String asked at Google/Amazon/Meta?
Subsequence counting and greedy string optimization problems are common in interviews at companies like Amazon, Google, and Meta. This problem tests understanding of subsequences, linear scans, and greedy decision making, which are frequent patterns in technical interviews.
What data structure is used in Maximize Number of Subsequences in a String?
The optimal solution primarily uses simple integer counters while scanning the string. Some alternative explanations use prefix sum arrays to track counts of characters before or after each position, but the greedy approach works with constant extra space.
What is the time complexity of Maximize Number of Subsequences in a String?
The optimal solution runs in O(n) time where n is the length of the input string. The algorithm performs a single pass to count characters and compute subsequences. Space complexity is O(1) because only a few counters are maintained.

Ready to solve this problem?

Practice Maximize Number of Subsequences in a String with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Common Subsequence