2.1.2. Two Pointers

2.1.2.1. Maximize Number of Subsequences in a String

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.

Example:

Input: text = “abdcdbc”, pattern = “ac”; Output: 4

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.

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.

---

• Intuition

If we add pattern[0], the best option is to add at the begin. If we add pattern[1], the best option is to add at the end.

• Corner case is when pattern[0] == pattern[1]

long long maximumSubsequenceCount(string text, string pattern) { // TC: O(N)
    long long r = 0, cnt1 = 0, cnt2 = 0;
    for (char& c: text) {
        if (c == pattern[1])
            r += cnt1, cnt2++;
        if (c == pattern[0]) // 💣
            cnt1++;
    }
    return r + max(cnt1, cnt2);
}

Firstly we’ll try to find the number of subquence pattern in the current string text. Iterate every character c from input string text, cnt1 means the count of character pattern[0], cnt2 means the count of character pattern[1]. If c == pattern[1], it can build up string pattern with every pattern[0] before it, so we update res += cnt1 as well as cnt2++.If c == pattern[0], we simply increment cnt1++. Then we consider of adding one more character. If we add pattern[0], the best option is to add at the begin, res += cnt2. If we add pattern[1], the best option is to add at the end, res += cnt1.