2207. Maximize Number of Subsequences in a String

Description

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.

Solutions

Solution 1: Traversal + Counting

Thinking

We may insert one character of \(pattern\) anywhere to maximize the number of \(pattern\) subsequences. \(|text| \le 10^5\), so recounting after every insertion is impossible.

Without insertion, a left-to-right scan works: \(x\) counts \(pattern[0]\) seen so far, and each \(pattern[1]\) adds \(x\). A single insertion only helps as a new prefix or a new suffix: inserting at the front adds the current number of \(pattern[1]\), inserting at the end adds the current number of \(pattern[0]\).

One scan yields the base answer together with \(x\) and \(y\); then add \(\max(x, y)\). When the two characters are equal, count \(pattern[1]\) before incrementing \(x\), so the current position is not paired with itself.

We can use two variables \(x\) and \(y\) to record the current counts of \(\textit{pattern}[0]\) and \(\textit{pattern}[1]\) in the string, respectively.

Then, traverse the string \(\textit{text}\). For the current character \(c\):

If \(c\) equals \(\textit{pattern}[1]\), increment \(y\) by one. At this point, all previously encountered \(\textit{pattern}[0]\) can form a \(\textit{pattern}\) subsequence with the current \(c\), so add \(x\) to the answer.
If \(c\) equals \(\textit{pattern}[0]\), increment \(x\) by one.

After the traversal, since we can insert one character, if we add \(\textit{pattern}[0]\) at the beginning of the string, we can get \(y\) \(\textit{pattern}\) subsequences. If we add \(\textit{pattern}[1]\) at the end of the string, we can get \(x\) \(\textit{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 \(\textit{text}\). The space complexity is \(O(1)\).

Python3JavaC++GoTypeScript

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

class Solution {
    public long maximumSubsequenceCount(String text, String pattern) {
        long ans = 0;
        int x = 0, y = 0;
        for (int i = 0; i < text.length(); ++i) {
            if (text.charAt(i) == pattern.charAt(1)) {
                ++y;
                ans += x;
            }
            if (text.charAt(i) == pattern.charAt(0)) {
                ++x;
            }
        }
        ans += Math.max(x, y);
        return ans;
    }
}

class Solution {
public:
    long long maximumSubsequenceCount(string text, string pattern) {
        long long ans = 0;
        int x = 0, y = 0;
        for (char& c : text) {
            if (c == pattern[1]) {
                ++y;
                ans += x;
            }
            if (c == pattern[0]) {
                ++x;
            }
        }
        ans += 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
}

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;
}

2207. Maximize Number of Subsequences in a String

Description

Solutions

Solution 1: Traversal + Counting

Comments