{x}
blog image

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.

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.

Solution Explanation: Maximize Number of Subsequences in a String

This problem asks us to find the maximum number of times a length-2 pattern can occur as a subsequence in a given string after adding either the first or second character of the pattern to the string exactly once.

Approach:

The core idea is to efficiently count the subsequences without explicitly generating all possible strings by adding characters. We leverage the fact that adding a character only increases the count of subsequences that start with the character we add.

  1. Initialization: We use x to count occurrences of pattern[0] and y to count occurrences of pattern[1] in the input string text. ans stores the total number of subsequences found so far.

  2. Iteration: We iterate through the input string.

    • If a character matches pattern[1], we increment y and add x to ans. This is because every occurrence of pattern[0] found before this point can now form a subsequence with the current pattern[1].
    • If a character matches pattern[0], we simply increment x.

  3. Adding a Character: After iterating, we consider the impact of adding a character.

    • Adding pattern[0] at the beginning would create y new subsequences (all existing pattern[1] can pair with the new pattern[0]).
    • Adding pattern[1] at the end would create x new subsequences (all existing pattern[0] can pair with the new pattern[1]).
    • We add the maximum of these two possibilities to ans.

  4. Return: Finally, we return ans, representing the maximum possible number of subsequences.

Time Complexity: O(n), where n is the length of the input string text. We iterate through the string once.

Space Complexity: O(1). We use a constant number of variables.

Code Implementation (Python):

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

Code Implementation (Java):

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

Code Implementation (C++):

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

The implementations in other languages (Go, TypeScript) follow a similar structure, adapting syntax as needed. The core logic remains consistent across all languages.