Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Maximize Number of Subsequences in a String solution and explanation

MediumGreedyPrefix SumString6 min read36.0% acceptanceUpdated 9 Apr 2026
Asked atAmazon
Practise Maximize Number of Subsequences in a String
14:11
2207. Maximize Number of Subsequences in a String || Biweekly Contest 74 || Leetcode 2207Bro Coders · 14:11 · 2K viewsWatch on YouTube
7 more videos on this problem
  1. 2207. Maximize Number of Subsequences in a String || Biweekly Contest 74 || Leetcode 2207Bro Coders · 14:11 · 2K views
  2. LeetCode 2207. Maximize Number of Subsequences in a String | Medium | 🏆 BiWeekly Contest 74Cherry Coding [IIT-G] · 18:02 · 635 views
  3. Leetcode BiWeekly 74 | 2207. Maximize Number of Subsequences in a StringcodingMohan · 13:03 · 559 views
  4. 2207. Maximize Number of Subsequences in a String (Leetcode Medium)Programming Live with Larry · 14:10 · 363 views
  5. Leetcode Biweekly Contest 74 | PROBLEM 2206 , 2207, 2208code Explainer · 14:40 · 318 views
  6. 2207. Maximize Number of Subsequences in a String | Leetcode Biweekly 74 | Leetcode easyBinaryMagic · 12:41 · 198 views
  7. LeetCode 2207. Maximize Number of Subsequences in a String | Medium | 🏆 BiWeekly Contest 74Cherry Coding [IIT-G] · 6:55 · 195 views
  8. LeetCode 2207: Maximize Number of Subsequences in a StringAlitaCode · 27:18 · 3 views

The 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 "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.

def maximize_subsequences(text, pattern):
    count_first = 0
    count_second = 0
    first, second = pattern[0], pattern[1]

    for ch in text:
        if ch == second:
            count_second += count_first
        if ch == first:
            count_first += 1

    max_first_insert = count_first + 1
    max_second_insert = count_second + count_first
    return max(max_first_insert, max_second_insert)

text = "abdcdbc"
pattern = "ac"
print(maximize_subsequences(text, pattern))
public class MaxSubsequences {
    public static int maximizeSubsequences(String text, String pattern) {
        int countFirst = 0, countSecond = 0;
        char first = pattern.charAt(0), second = pattern.charAt(1);

        for (char c : text.toCharArray()) {
            if (c == second) countSecond += countFirst;
            if (c == first) countFirst++;
        }

        int maxFirstInsert = countFirst + 1;
        int maxSecondInsert = countSecond + countFirst;
        return Math.max(maxFirstInsert, maxSecondInsert);
    }

    public static void main(String[] args) {
        String text = "abdcdbc";
        String pattern = "ac";
        System.out.println(maximizeSubsequences(text, pattern));
    }
}
#include <iostream>
#include <string>

int maximizeSubsequences(std::string text, std::string pattern) {
    int countFirst = 0, countSecond = 0;
    int maxSubsequences = 0;
    char first = pattern[0], second = pattern[1];

    for (char& ch : text) {
        if (ch == second) countSecond += countFirst;
        if (ch == first) countFirst++;
    }

    int maxFirstInsert = countFirst + 1;
    int maxSecondInsert = countSecond + countFirst;
    return std::max(maxFirstInsert, maxSecondInsert);
}

int main() {
    std::string text = "abdcdbc";
    std::string pattern = "ac";
    std::cout << maximizeSubsequences(text, pattern);
    return 0;
}
function maximizeSubsequences(text, pattern) {
    let countFirst = 0;
    let countSecond = 0;
    const first = pattern[0];
    const second = pattern[1];

    for (let ch of text) {
        if (ch === second) countSecond += countFirst;
        if (ch === first) countFirst++;
    }

    const maxFirstInsert = countFirst + 1;
    const maxSecondInsert = countSecond + countFirst;
    return Math.max(maxFirstInsert, maxSecondInsert);
}

const text = "abdcdbc";
const pattern = "ac";
console.log(maximizeSubsequences(text, pattern));
#include <stdio.h>
#include <string.h>

int maximizeSubsequences(char* text, char* pattern) {
    int countFirst = 0, countSecond = 0;
    int length = strlen(text);
    int maxSubsequences = 0;
    char first = pattern[0], second = pattern[1];

    for (int i = 0; i < length; i++) {
        if (text[i] == second) {
            countSecond += countFirst;
        }
        if (text[i] == first) {
            countFirst++;
        }
    }

    int maxFirstInsert = countFirst + 1;
    int maxSecondInsert = countSecond + countFirst;
    return maxFirstInsert > maxSecondInsert ? maxFirstInsert : maxSecondInsert;
}

int main() {
    char text[] = "abdcdbc";
    char pattern[] = "ac";
    printf("%d", maximizeSubsequences(text, pattern));
    return 0;
}
using System;

class Program {
    static int MaximizeSubsequences(string text, string pattern) {
        int countFirst = 0, countSecond = 0;
        char first = pattern[0], second = pattern[1];

        foreach (char c in text) {
            if (c == second) countSecond += countFirst;
            if (c == first) countFirst++;
        }

        int maxFirstInsert = countFirst + 1;
        int maxSecondInsert = countSecond + countFirst;
        return Math.Max(maxFirstInsert, maxSecondInsert);
    }

    static void Main() {
        string text = "abdcdbc";
        string pattern = "ac";
        Console.WriteLine(MaximizeSubsequences(text, pattern));
    }
}

This Python version simplifies subsequence counting with dynamic counting of pattern characters' impact on possible subsequences.

Complexity

Time complexity is O(n) where n is the length of the text; Space complexity is O(1).

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.

def count_subsequences(s, pattern):
    first_count, total_count = 0, 0
    for ch in s:
        if ch == pattern[1]:
            total_count += first_count
        if ch == pattern[0]:
            first_count += 1
    return total_count


def maximize_subsequences(text, pattern):
    max_count = 0
    for i in range(len(text) + 1):
        modified_text = text[:i] + pattern[0] + text[i:]
        count = count_subsequences(modified_text, pattern)
        max_count = max(max_count, count)

        modified_text = text[:i] + pattern[1] + text[i:]
        count = count_subsequences(modified_text, pattern)
        max_count = max(max_count, count)

    return max_count

text = "abdcdbc"
pattern = "ac"
print(maximize_subsequences(text, pattern))
public class MaxSubsequenceSimulation {
    public static int countSubsequences(String s, String pattern) {
        int firstCount = 0, totalCount = 0;
        for (char ch : s.toCharArray()) {
            if (ch == pattern.charAt(1)) totalCount += firstCount;
            if (ch == pattern.charAt(0)) firstCount++;
        }
        return totalCount;
    }

    public static int maximizeSubsequences(String text, String pattern) {
        int maxCount = 0;
        for (int i = 0; i <= text.length(); i++) {
            String modifiedText = text.substring(0, i) + pattern.charAt(0) + text.substring(i);
            int count = countSubsequences(modifiedText, pattern);
            maxCount = Math.max(maxCount, count);

            modifiedText = text.substring(0, i) + pattern.charAt(1) + text.substring(i);
            count = countSubsequences(modifiedText, pattern);
            maxCount = Math.max(maxCount, count);
        }
        return maxCount;
    }

    public static void main(String[] args) {
        String text = "abdcdbc";
        String pattern = "ac";
        System.out.println(maximizeSubsequences(text, pattern));
    }
}
#include <iostream>
#include <string>

int countSubsequences(const std::string& s, const std::string& pattern) {
    int firstCount = 0, totalCount = 0;
    for (char ch : s) {
        if (ch == pattern[1]) totalCount += firstCount;
        if (ch == pattern[0]) firstCount++;
    }
    return totalCount;
}

int maximizeSubsequences(std::string text, std::string pattern) {
    int maxCount = 0;
    for (size_t i = 0; i <= text.length(); ++i) {
        std::string modifiedText = text.substr(0, i) + pattern[0] + text.substr(i);
        int count = countSubsequences(modifiedText, pattern);
        maxCount = std::max(maxCount, count);

        modifiedText = text.substr(0, i) + pattern[1] + text.substr(i);
        count = countSubsequences(modifiedText, pattern);
        maxCount = std::max(maxCount, count);
    }
    return maxCount;
}

int main() {
    std::string text = "abdcdbc";
    std::string pattern = "ac";
    std::cout << maximizeSubsequences(text, pattern);
    return 0;
}
function countSubsequences(s, pattern) {
    let firstCount = 0, totalCount = 0;
    for (let ch of s) {
        if (ch === pattern[1]) totalCount += firstCount;
        if (ch === pattern[0]) firstCount++;
    }
    return totalCount;
}

function maximizeSubsequences(text, pattern) {
    let maxCount = 0;
    for (let i = 0; i <= text.length; i++) {
        let modifiedText = text.slice(0, i) + pattern[0] + text.slice(i);
        let count = countSubsequences(modifiedText, pattern);
        maxCount = Math.max(maxCount, count);

        modifiedText = text.slice(0, i) + pattern[1] + text.slice(i);
        count = countSubsequences(modifiedText, pattern);
        maxCount = Math.max(maxCount, count);
    }
    return maxCount;
}

const text = "abdcdbc";
const pattern = "ac";
console.log(maximizeSubsequences(text, pattern));
#include <stdio.h>
#include <string.h>

int countSubsequences(char* s, char* pattern) {
    int firstCount = 0, totalCount = 0;
    for (int i = 0; s[i]; i++) {
        if (s[i] == pattern[1]) totalCount += firstCount;
        if (s[i] == pattern[0]) firstCount++;
    }
    return totalCount;
}

int maximizeSubsequences(char* text, char* pattern) {
    int length = strlen(text);
    int maxCount = 0;
    for (int i = 0; i <= length; i++) {
        char modifiedText[length + 2];
        strncpy(modifiedText, text, i);
        modifiedText[i] = pattern[0];
        strcpy(modifiedText + i + 1, text + i);
        int count = countSubsequences(modifiedText, pattern);
        if (count > maxCount) maxCount = count;

        modifiedText[i] = pattern[1];
        count = countSubsequences(modifiedText, pattern);
        if (count > maxCount) maxCount = count;
    }
    return maxCount;
}

int main() {
    char text[] = "abdcdbc";
    char pattern[] = "ac";
    printf("%d", maximizeSubsequences(text, pattern));
    return 0;
}
using System;

class Program {
    static int CountSubsequences(string s, string pattern) {
        int firstCount = 0, totalCount = 0;
        foreach (char ch in s) {
            if (ch == pattern[1]) totalCount += firstCount;
            if (ch == pattern[0]) firstCount++;
        }
        return totalCount;
    }

    static int MaximizeSubsequences(string text, string pattern) {
        int maxCount = 0;
        for (int i = 0; i <= text.Length; i++) {
            string modifiedText = text.Insert(i, pattern[0].ToString());
            int count = CountSubsequences(modifiedText, pattern);
            maxCount = Math.Max(maxCount, count);

            modifiedText = text.Insert(i, pattern[1].ToString());
            count = CountSubsequences(modifiedText, pattern);
            maxCount = Math.Max(maxCount, count);
        }
        return maxCount;
    }

    static void Main() {
        string text = "abdcdbc";
        string pattern = "ac";
        Console.WriteLine(MaximizeSubsequences(text, pattern));
    }
}

In Python, string slicing and concatenation allow each potential insertion to generate new sequences to check, counting subsequence matches efficiently after each.

Complexity

Time complexity is O(n2); Space complexity is O(n).

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

function maximumSubsequenceCount(text: string, pattern: string): number {
    let ans = 0;
    let [x, y] = [0, 0];
    for (const c of text) {
        if (c === pattern[1]) {
            ++y;
            ans += x;
        }
        if (c === pattern[0]) {
            ++x;
        }
    }
    ans += Math.max(x, y);
    return ans;
}
func maximumSubsequenceCount(text string, pattern string) (ans int64) {
	x, y := 0, 0
	for _, c := range text {
		if byte(c) == pattern[1] {
			y++
			ans += int64(x)
		}
		if byte(c) == pattern[0] {
			x++
		}
	}
	ans += int64(max(x, y))
	return
}
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).

Approach 2: Simulation with Detailed Insertion Check

Time complexity is O(n2); Space complexity is O(n).

Traversal + Counting–

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

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.

Comments

Next problem · similarLongest Common SubsequenceMedium
Now write it yourselfClose this page and solve Maximize Number of Subsequences in a String in the editor, without looking.
Practise Maximize Number of Subsequences in a String