Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2207.html
2207. Maximize Number of Subsequences in a String (Medium)
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 <= 105pattern.length == 2textandpatternconsist only of lowercase English letters.
Similar Questions:
Solution 1. Prefix Sum and Suffix Sum
Step 1: count the number of subsequences in s without insertion as sum.
Step 2: At each index i, let a be the count of p[0] in prefix, and b be the count of p[1] in the suffix.
If we append p[0], we get sum + b subsequences. IF we append p[1], we get sum + a subsequences.
-
// OJ: https://leetcode.com/problems/maximize-number-of-subsequences-in-a-string/ // Time: O(N) // Space: O(1) class Solution { public: long long maximumSubsequenceCount(string s, string p) { long a = 0, b = 0, sum = 0; for (char c : s) b += c == p[1]; long tmp = b; for (char c : s) { tmp -= c == p[1]; if (c == p[0]) sum += tmp; } long ans = b; for (char c : s) { a += c == p[0]; b -= c == p[1]; ans = max({ ans, b, a }); } return sum + ans; } }; -
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 ############ # 2207. Maximize Number of Subsequences in a String # https://leetcode.com/problems/maximize-number-of-subsequences-in-a-string class Solution: def maximumSubsequenceCount(self, text: str, pattern: str) -> int: p1, p2 = pattern if p1 == p2: n = text.count(p1) + 1 return n * (n - 1) // 2 def count(s): res = curr = 0 for x in s: if x == p1: curr += 1 elif x == p2: res += curr return res return max(count(p1 + text), count(text + p2)) -
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; } } -
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) } func max(a, b int) int { if a > b { return a } return b }
In fact, we can see that, we just need the global maximum of all a and b values. This leads to solution 2.
Solution 2. Prefix Sum and Suffix Sum
If we add p[0], the best option is to prepend it at the beginning.
If we add p[1], the best option is to append it at the end.
-
// OJ: https://leetcode.com/problems/maximize-number-of-subsequences-in-a-string/ // Time: O(N) // Space: O(1) class Solution { public: long long maximumSubsequenceCount(string s, string p) { long a = 0, b = 0, sum = 0; for (char c : s) { if (c == p[1]) sum += a; a += c == p[0]; b += c == p[1]; } return sum + max(a, b); } }; -
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 ############ # 2207. Maximize Number of Subsequences in a String # https://leetcode.com/problems/maximize-number-of-subsequences-in-a-string class Solution: def maximumSubsequenceCount(self, text: str, pattern: str) -> int: p1, p2 = pattern if p1 == p2: n = text.count(p1) + 1 return n * (n - 1) // 2 def count(s): res = curr = 0 for x in s: if x == p1: curr += 1 elif x == p2: res += curr return res return max(count(p1 + text), count(text + p2)) -
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; } } -
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) } func max(a, b int) int { if a > b { return a } return b }
Discuss
https://leetcode.com/problems/maximize-number-of-subsequences-in-a-string/discuss/1863963