Maximize Number of Subsequences in a 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 themaximum number of times pattern _can occur as asubsequence 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.

Examples

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

Solution

Method 1 – Greedy Counting and Insertion

Intuition

To maximize the number of subsequences equal to pattern, we can insert either pattern[0] or pattern[1] anywhere in the string. The best strategy is to insert the character that increases the count the most. We count the number of subsequences for both options and return the maximum.

Approach

1. Count the number of pattern[0] and pattern[1] in text.
2. Count the number of subsequences of pattern in text.
3. Try inserting pattern[0] at every position: this increases the number of pattern[0] by 1, so the number of subsequences increases by the number of pattern[1] in text.
4. Try inserting pattern[1] at every position: this increases the number of pattern[1] by 1, so the number of subsequences increases by the number of pattern[0] in text.
5. Return the maximum of the two options.

Code

C++

class Solution {
public:
    long long maximumSubsequenceCount(string text, string pattern) {
        long long cnt0 = 0, cnt1 = 0, ans = 0;
        for (char c : text) {
            if (c == pattern[1]) ans += cnt0;
            if (c == pattern[0]) cnt0++;
        }
        cnt0 = cnt1 = 0;
        for (char c : text) {
            if (c == pattern[0]) cnt0++;
            if (c == pattern[1]) cnt1++;
        }
        return max(ans + cnt0, ans + cnt1);
    }
};

Go

func maximumSubsequenceCount(text string, pattern string) int64 {
    cnt0, cnt1, ans := int64(0), int64(0), int64(0)
    for _, c := range text {
        if byte(c) == pattern[1] {
            ans += cnt0
        }
        if byte(c) == pattern[0] {
            cnt0++
        }
    }
    cnt0, cnt1 = 0, 0
    for _, c := range text {
        if byte(c) == pattern[0] {
            cnt0++
        }
        if byte(c) == pattern[1] {
            cnt1++
        }
    }
    if ans+cnt0 > ans+cnt1 {
        return ans + cnt0
    }
    return ans + cnt1
}

Java

class Solution {
    public long maximumSubsequenceCount(String text, String pattern) {
        long cnt0 = 0, cnt1 = 0, ans = 0;
        for (char c : text.toCharArray()) {
            if (c == pattern.charAt(1)) ans += cnt0;
            if (c == pattern.charAt(0)) cnt0++;
        }
        cnt0 = cnt1 = 0;
        for (char c : text.toCharArray()) {
            if (c == pattern.charAt(0)) cnt0++;
            if (c == pattern.charAt(1)) cnt1++;
        }
        return Math.max(ans + cnt0, ans + cnt1);
    }
}

Kotlin

class Solution {
    fun maximumSubsequenceCount(text: String, pattern: String): Long {
        var cnt0 = 0L
        var cnt1 = 0L
        var ans = 0L
        for (c in text) {
            if (c == pattern[1]) ans += cnt0
            if (c == pattern[0]) cnt0++
        }
        cnt0 = 0L
        cnt1 = 0L
        for (c in text) {
            if (c == pattern[0]) cnt0++
            if (c == pattern[1]) cnt1++
        }
        return maxOf(ans + cnt0, ans + cnt1)
    }
}

Python

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

Rust

impl Solution {
    pub fn maximum_subsequence_count(text: String, pattern: String) -> i64 {
        let (mut cnt0, mut cnt1, mut ans) = (0i64, 0i64, 0i64);
        let t = text.as_bytes();
        let p = pattern.as_bytes();
        for &c in t {
            if c == p[1] { ans += cnt0; }
            if c == p[0] { cnt0 += 1; }
        }
        cnt0 = 0;
        cnt1 = 0;
        for &c in t {
            if c == p[0] { cnt0 += 1; }
            if c == p[1] { cnt1 += 1; }
        }
        ans + cnt0
    }
}

TypeScript

class Solution {
    maximumSubsequenceCount(text: string, pattern: string): number {
        let cnt0 = 0, cnt1 = 0, ans = 0
        for (const c of text) {
            if (c === pattern[1]) ans += cnt0
            if (c === pattern[0]) cnt0++
        }
        cnt0 = 0
        cnt1 = 0
        for (const c of text) {
            if (c === pattern[0]) cnt0++
            if (c === pattern[1]) cnt1++
        }
        return Math.max(ans + cnt0, ans + cnt1)
    }
}

Complexity

• ⏰ Time complexity: O(n) — single pass for counting and another for totals.
• 🧺 Space complexity: O(1) — only a few variables are used.