[LeetCode] 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 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:

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.

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

Approach: Given the pattern has just 2 characters, our tasks becomes easy. Let's take an example and see:

Say the text is "abaab" and pattern is "ab". Now let's traverse text from beginning. Whenever we see 'b' in the text the number of subsequence till index of current 'b' will be equal to the number of 'a's before 'b'. Right. That's how we can count the number of subsequence in existing text.

Now lets see how we can place pattern[0] or pattern[1] to gain maximum number of subsequence. With the above approach we can see that the best place to place pattern[0] is at the beginning and for pattern[1] is end of the text so we can increase the existing subsequence count by the max of Count(pattern[0]) and Count(pattern[1]).

There is a corner case here where pattern[0] and pattern[1] are same like "aa". In this case we can see the final answer will be 1 + 2 + 3 + ...... + count(pattern[0]). 

That's all!

Implementation in C#:

    public long MaximumSubsequenceCount(string text, string pattern)

    {

        long firstCount = 0;

        long secondCount = 0;

        long subSeqCount = 0;

        foreach (char ch in text)

        {

            if (ch == pattern[0])

            {

                ++firstCount;

            }

            else if (ch == pattern[1])

            {

                ++secondCount;

                subSeqCount += firstCount;

            }

        }

        if (pattern[0] == pattern[1])

        {

            return ((firstCount * (firstCount + 1)) / 2);

        }

        subSeqCount += Math.Max(firstCount, secondCount);

        return subSeqCount;

    }

Complexity: O(n)