# Maximize Number of Subsequences in a String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximize-number-of-subsequences-in-a-string)
Canonical: https://scaleengineer.com/dsa/problems/maximize-number-of-subsequences-in-a-string
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** String
---
## Problem
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 "ab**a**dcdbc". 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 "**a**abdcdbc" and "abd**a**cdbc".
However, strings such as "abdc**a**dbc", "abd**c**cdbc", and "abdcdbc**c**", 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 "**a**aabb", "aa**a**bb", and "aab**b**b".

**Constraints:**

* `1 <= text.length <= 105`
* `pattern.length == 2`
* `text` and `pattern` consist only of lowercase English letters.

# Approaches
## Brute Force Simulation
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public long maximumSubsequenceCount(String text, String pattern) {
        long maxCount = 0;
        char p1 = pattern.charAt(0);
        char p2 = pattern.charAt(1);

        // Option 1: Try inserting pattern[0] at all possible positions
        for (int i = 0; i <= text.length(); i++) {
            StringBuilder sb = new StringBuilder(text);
            sb.insert(i, p1);
            maxCount = Math.max(maxCount, countSubsequences(sb.toString(), pattern));
        }

        // Option 2: Try inserting pattern[1] at all possible positions
        for (int i = 0; i <= text.length(); i++) {
            StringBuilder sb = new StringBuilder(text);
            sb.insert(i, p2);
            maxCount = Math.max(maxCount, countSubsequences(sb.toString(), pattern));
        }

        return maxCount;
    }

    private long countSubsequences(String s, String p) {
        char p1 = p.charAt(0);
        char p2 = p.charAt(1);
        long count1 = 0;
        long totalSubsequences = 0;

        for (char c : s.toCharArray()) {
            // This order handles the case where p1 == p2 correctly.
            // We count pairs of (p1_i, p2_j) where i < j.
            if (c == p2) {
                totalSubsequences += count1;
            }
            if (c == p1) {
                count1++;
            }
        }
        return totalSubsequences;
    }
}
```
### 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`.

## Greedy Single-Pass Approach
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.
**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.
**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.
### Explanation
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 `p2`s. 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 `p1`s 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 `p1`s. 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.

```java
class Solution {
    public long maximumSubsequenceCount(String text, String pattern) {
        long res = 0;
        long count1 = 0; // count of pattern[0]
        long count2 = 0; // count of pattern[1]
        char p1 = pattern.charAt(0);
        char p2 = pattern.charAt(1);

        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            if (c == p2) {
                // This p2 forms subsequences with all p1's seen so far.
                res += count1;
                count2++;
            }
            // Use a separate if, not else-if, to handle the p1 == p2 case.
            if (c == p1) {
                // This is a new p1.
                count1++;
            }
        }

        // After iterating, 'res' is the original count of subsequences.
        // 'count1' and 'count2' are the total counts of p1 and p2.
        // Adding p1 at the beginning adds 'count2' new subsequences.
        // Adding p2 at the end adds 'count1' new subsequences.
        // We take the better of these two options.
        return res + Math.max(count1, count2);
    }
}
```
### 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 `p1`s 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)`.

# Solutions
### Java

```java
class Solution {
public
  long maximumSubsequenceCount(String text, String pattern) {
    int[] cnt = new int[26];
    char a = pattern.charAt(0);
    char b = pattern.charAt(1);
    long ans = 0;
    for (char c : text.toCharArray()) {
      if (c == b) {
        ans += cnt[a - 'a'];
      }
      cnt[c - 'a']++;
    }
    ans += Math.max(cnt[a - 'a'], cnt[b - 'a']);
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maximumSubsequenceCount(string text, string pattern) {
    long long ans = 0;
    char a = pattern[0], b = pattern[1];
    vector<int> cnt(26);
    for (char &c : text) {
      if (c == b)
        ans += cnt[a - 'a'];
      cnt[c - 'a']++;
    }
    ans += max(cnt[a - 'a'], cnt[b - 'a']);
    return ans;
  }
};

```

### Python

```python
class Solution:
    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

```