Question

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

Solutions

Solution 1

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

class Solution {
  public long maximumSubsequenceCount(String text, String pattern) {
    int[] cnt = new int[26];
    char a = pattern.charAt(0);
    char b = pattern.charAt(1);
    long ans = 0;
    for (char c : text.toCharArray()) {
      if (c == b) {
        ans += cnt[a - 'a'];
      }
      cnt[c - 'a']++;
    }
    ans += Math.max(cnt[a - 'a'], cnt[b - 'a']);
    return ans;
  }
}

class Solution {
public:
  long long maximumSubsequenceCount(string text, string pattern) {
    long long ans = 0;
    char a = pattern[0], b = pattern[1];
    vector<int> cnt(26);
    for (char& c : text) {
      if (c == b) ans += cnt[a - 'a'];
      cnt[c - 'a']++;
    }
    ans += max(cnt[a - 'a'], cnt[b - 'a']);
    return ans;
  }
};

func maximumSubsequenceCount(text string, pattern string) int64 {
  ans := 0
  cnt := make([]int, 26)
  a, b := pattern[0], pattern[1]
  for i := range text {
    c := text[i]
    if c == b {
      ans += cnt[a-'a']
    }
    cnt[c-'a']++
  }
  ans += max(cnt[a-'a'], cnt[b-'a'])
  return int64(ans)
}