Maximize Number of Subsequences in a String

Med

#2010Time: O(N^2), where N is the length of `text`. There are O(N) possible insertion points. For each, we create a new string (O(N)) and then count subsequences (O(N)). This leads to a total time complexity of O(N * N).Space: O(N), where N is the length of `text`. In each iteration of the main loop, a new `StringBuilder` or string of length N+1 is created to store the modified text.

Patterns

Greedy Prefix Sum

Data structures

String

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. It considers every possible way to modify the string text by inserting pattern[0] or pattern[1] at each possible position. For each of these 2 * (N+1) modified strings, it calculates the number of pattern subsequences and keeps track of the maximum count found.

Algorithm

Initialize a variable maxCount to 0.
Iterate through all possible insertion indices i from 0 to text.length().
- Create a new string s1 by inserting pattern[0] at index i in text.
- Calculate the number of pattern subsequences in s1 using a helper function.
- Update maxCount = max(maxCount, new_count).
Iterate again through all possible insertion indices i from 0 to text.length().
- Create a new string s2 by inserting pattern[1] at index i in text.
- Calculate the number of pattern subsequences in s2.
- Update maxCount = max(maxCount, new_count).
Return maxCount.

Subsequence Counting Helper:

The helper function takes a string s and the pattern.
It iterates through s, maintaining a count of pattern[0] occurrences (count1).
When it encounters pattern[1], it adds the current count1 to the total subsequence count.
This helper runs in O(L) time, where L is the length of the string s.

Walkthrough

This method exhaustively checks every single possibility. There are text.length() + 1 positions to insert a character. Since we can insert either pattern[0] or pattern[1], we have a total of 2 * (text.length() + 1) potential new strings to evaluate.

For each of these potential strings, we must calculate how many times the pattern appears as a subsequence. A helper function can do this efficiently in linear time relative to the string's length. This helper iterates through the string, keeping a running count of the first character of the pattern. Whenever the second character is encountered, the current count of the first character is added to the total subsequence count.

The main function calls this helper for every generated string and keeps track of the maximum value seen, which is the final answer.

1class Solution {2    public long maximumSubsequenceCount(String text, String pattern) {3        long maxCount = 0;4        char p1 = pattern.charAt(0);5        char p2 = pattern.charAt(1);6 7        // Option 1: Try inserting pattern[0] at all possible positions8        for (int i = 0; i <= text.length(); i++) {9            StringBuilder sb = new StringBuilder(text);10            sb.insert(i, p1);11            maxCount = Math.max(maxCount, countSubsequences(sb.toString(), pattern));12        }13 14        // Option 2: Try inserting pattern[1] at all possible positions15        for (int i = 0; i <= text.length(); i++) {16            StringBuilder sb = new StringBuilder(text);17            sb.insert(i, p2);18            maxCount = Math.max(maxCount, countSubsequences(sb.toString(), pattern));19        }20 21        return maxCount;22    }23 24    private long countSubsequences(String s, String p) {25        char p1 = p.charAt(0);26        char p2 = p.charAt(1);27        long count1 = 0;28        long totalSubsequences = 0;29 30        for (char c : s.toCharArray()) {31            // This order handles the case where p1 == p2 correctly.32            // We count pairs of (p1_i, p2_j) where i < j.33            if (c == p2) {34                totalSubsequences += count1;35            }36            if (c == p1) {37                count1++;38            }39        }40        return totalSubsequences;41    }42}

Complexity

Time

O(N^2), where N is the length of `text`. There are O(N) possible insertion points. For each, we create a new string (O(N)) and then count subsequences (O(N)). This leads to a total time complexity of O(N * N).

Space

O(N), where N is the length of `text`. In each iteration of the main loop, a new `StringBuilder` or string of length N+1 is created to store the modified text.

Trade-offs

Pros

Simple to understand and implement as it directly models the problem statement.
Guaranteed to be correct as it checks every possibility.

Cons

Highly inefficient due to its quadratic time complexity.
Generates many temporary strings, leading to high memory usage and garbage collection overhead.
Will result in a 'Time Limit Exceeded' error on platforms with strict time limits for the given constraints.

A much more efficient approach is to use a greedy strategy based on a key insight: to maximize the number of new subsequences, the added character must be placed in the most optimal position. Adding pattern[0] at the beginning of text maximizes its contribution, and adding pattern[1] at the end of text maximizes its contribution. This allows us to calculate the result in a single pass without any string modifications.

Algorithm

Let p1 = pattern.charAt(0) and p2 = pattern.charAt(1).
Initialize originalCount = 0L, count1 = 0L (for p1), and count2 = 0L (for p2).
Iterate through each character c of the input text:
- If c is equal to p2, it forms a subsequence with all p1s encountered so far. Add the current count1 to originalCount. Then, increment count2.
- If c is equal to p1, increment count1.
- Note: If p1 and p2 are the same character, both if conditions will be met. The order of operations (updating originalCount before count1) is crucial for correctness.
After the loop, originalCount holds the number of subsequences in the original string. count1 and count2 hold the total counts of p1 and p2.
The maximum number of new subsequences we can form is max(count1, count2). This is achieved by adding p1 at the start (gaining count2 subsequences) or p2 at the end (gaining count1 subsequences).
The final result is originalCount + max(count1, count2).

Walkthrough

Instead of simulating every possible insertion, we can analyze the effect of an insertion. When we add a character, it contributes to new subsequences based on its position relative to the other character in the pattern.

Adding pattern[0] (p1): A new p1 will form subsequences with all existing pattern[1] (p2) that appear after it. To maximize this, we should place the new p1 at the very beginning of the string (index 0). This way, it precedes all existing p2s. The number of new subsequences formed will be exactly the total count of p2 in the original text.
Adding pattern[1] (p2): A new p2 will form subsequences with all existing p1s that appear before it. To maximize this, we should place the new p2 at the very end of the string. This way, it follows all existing p1s. The number of new subsequences formed will be exactly the total count of p1 in the original text.

Therefore, the problem reduces to finding the original number of subsequences and adding the better of the two options: count(p2) or count(p1). We can calculate all three values (original_count, count(p1), count(p2)) in a single pass.

1class Solution {2    public long maximumSubsequenceCount(String text, String pattern) {3        long res = 0;4        long count1 = 0; // count of pattern[0]5        long count2 = 0; // count of pattern[1]6        char p1 = pattern.charAt(0);7        char p2 = pattern.charAt(1);8 9        for (int i = 0; i < text.length(); i++) {10            char c = text.charAt(i);11            if (c == p2) {12                // This p2 forms subsequences with all p1's seen so far.13                res += count1;14                count2++;15            }16            // Use a separate if, not else-if, to handle the p1 == p2 case.17            if (c == p1) {18                // This is a new p1.19                count1++;20            }21        }22 23        // After iterating, 'res' is the original count of subsequences.24        // 'count1' and 'count2' are the total counts of p1 and p2.25        // Adding p1 at the beginning adds 'count2' new subsequences.26        // Adding p2 at the end adds 'count1' new subsequences.27        // We take the better of these two options.28        return res + Math.max(count1, count2);29    }30}

Complexity

Time

O(N), where N is the length of `text`. The algorithm involves a single pass through the input string to calculate all necessary counts.

Space

O(1). The algorithm only uses a few constant-size variables (`long`, `char`) to store counts, regardless of the input string's size.

Trade-offs

Pros

Extremely efficient with linear time complexity.
Optimal space complexity, using only a few extra variables.
Avoids costly string manipulation and object creation overhead.

Cons

The logic is less direct than the brute-force approach and requires a key insight about the optimal insertion points.

Solutions

Solution

1class Solution {2public3  long maximumSubsequenceCount(String text, String pattern) {4    int[] cnt = new int[26];5    char a = pattern.charAt(0);6    char b = pattern.charAt(1);7    long ans = 0;8    for (char c : text.toCharArray()) {9      if (c == b) {10        ans += cnt[a - 'a'];11      }12      cnt[c - 'a']++;13    }14    ans += Math.max(cnt[a - 'a'], cnt[b - 'a']);15    return ans;16  }17}

1class Solution {2public:3  long long maximumSubsequenceCount(string text, string pattern) {4    long long ans = 0;5    char a = pattern[0], b = pattern[1];6    vector<int> cnt(26);7    for (char &c : text) {8      if (c == b)9        ans += cnt[a - 'a'];10      cnt[c - 'a']++;11    }12    ans += max(cnt[a - 'a'], cnt[b - 'a']);13    return ans;14  }15};

1class Solution:2    def maximumSubsequenceCount(self, text: str, pattern: str) -> int: ans = 0 cnt = Counter() for c in text: if c == pattern[1]: ans += cnt[pattern[0]] cnt[c] += 1 ans += max(cnt[pattern[0]], cnt[pattern[1]]) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem