Maximum Number of Subsequences After One Inserting - Solution & Explanation

Problem Overview: You are given a string s and a two‑character pattern. You may insert exactly one character anywhere in the string. The goal is to maximize how many times the pattern appears as a subsequence after the insertion.

The subsequence condition means characters do not need to be adjacent, only ordered. The key decision is which character to insert and where it contributes the most subsequences. Because the pattern length is fixed at two, the problem reduces to counting how many valid pairs can be formed.

Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)

Try inserting either character of the pattern at every possible index from 0 to n. After each insertion, scan the entire string and count how many subsequences match the pattern. Counting subsequences can be done by iterating through the string while tracking how many occurrences of the first pattern character have appeared so far. Each time the second character appears, add the current count of the first character. This approach is straightforward but expensive because you repeat the full counting step for every insertion position.

Approach 2: Greedy Enumeration with Prefix Counting (O(n) time, O(1) space)

Observe that inserting the first character of the pattern increases subsequences formed with all existing occurrences of the second character. Inserting the second character increases subsequences formed with all previous occurrences of the first character. Because only two characters are possible insertion choices, you only need to evaluate two scenarios.

First compute the number of subsequences already present in s. Iterate through the string while counting how many times the first pattern character has appeared. Every time the second pattern character appears, add the current count. Then compute the potential gain: inserting the first character at the beginning pairs with every existing second character, while inserting the second character at the end pairs with every existing first character. The maximum of these two options gives the optimal result. This works because the best insertion location always maximizes pair formation globally rather than locally.

This solution relies on linear scans and simple counters. The idea closely resembles techniques used in greedy optimization combined with counting patterns inside a string. The counting process is essentially a running accumulation similar to a prefix sum over character frequencies.

Recommended for interviews: The greedy enumeration approach with prefix counting is what interviewers expect. The brute force method demonstrates understanding of subsequence counting, but the O(n) solution shows you can reason about how insertion affects pair formation and avoid unnecessary recomputation.