2207. Maximize Number of Subsequences in a String LeetCode Solution
In this guide, you will get 2207. Maximize Number of Subsequences in a String LeetCode Solution with the best time and space complexity. The solution to Maximize Number of Subsequences in a String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
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.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
2207. Maximize Number of Subsequences in a String LeetCode Solution in C++
class Solution {
public:
long long maximumSubsequenceCount(string text, string pattern) {
long ans = 0;
int count0 = 0; // the count of the letter pattern[0]
int count1 = 0; // the count of the letter pattern[1]
for (const char c : text) {
if (c == pattern[1]) {
ans += count0;
++count1;
}
if (c == pattern[0])
++count0;
}
// It is optimal to add pattern[0] at the beginning or add pattern[1] at the
// end of the text.
return ans + max(count0, count1);
}
}; /* code provided by PROGIEZ */
2207. Maximize Number of Subsequences in a String LeetCode Solution in Java
class Solution {
public long maximumSubsequenceCount(String text, String pattern) {
long ans = 0;
int count0 = 0; // the count of the letter pattern[0]
int count1 = 0; // the count of the letter pattern[1]
for (final char c : text.toCharArray()) {
if (c == pattern.charAt(1)) {
ans += count0;
++count1;
}
if (c == pattern.charAt(0))
++count0;
}
// It is optimal to add pattern[0] at the beginning or add pattern[1] at the
// end of the text.
return ans + Math.max(count0, count1);
}
} // code provided by PROGIEZ
2207. Maximize Number of Subsequences in a String LeetCode Solution in Python
class Solution:
def maximumSubsequenceCount(self, text: str, pattern: str) -> int:
ans = 0
count0 = 0 # the count of the letter pattern[0]
count1 = 0 # the count of the letter pattern[1]
for c in text:
if c == pattern[1]:
ans += count0
count1 += 1
if c == pattern[0]:
count0 += 1
# It is optimal to add pattern[0] at the beginning or add pattern[1] at the
# end of the text.
return ans + max(count0, count1) # code by PROGIEZ
