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 "ab*adcdbc". 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", "aa*abb", and "aabb*b".
Constraints:
-
1 <= text.length <= 105
-
pattern.length == 2
-
text
andpattern
consist only of lowercase English letters.
SOLUTION:
class Solution:
def countSub(self, a, b):
m = len(a)
n = len(b)
dp = [[0 for i in range(n + 1)] for j in range(m + 1)]
for i in range(n + 1):
dp[0][i] = 0
for i in range(m + 1):
dp[i][0] = 1
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j]
return dp[m][n]
def maximumSubsequenceCount(self, text: str, pattern: str) -> int:
n = len(text)
mxsub = self.countSub(text, pattern)
a = text.count(pattern[0])
b = text.count(pattern[1])
return mxsub + max(a, b)
# pos = []
# for i in range(n):
# if text[i] in pattern:
# pos.append(i)
# pos.append(i + 1)
# for i in pos:
# for j in range(2):
# val = self.countSub(text[:i] + pattern[j] + text[i:], pattern)
# mxsub = max(mxsub, val)
# return mxsub
Top comments (0)