문자열의 하위 시퀀스 수 최대화

인덱스가 0인 문자열text과 길이가 pattern인 또 다른 인덱스가 0인 문자열2이 제공되며 둘 다 영어 소문자로만 구성됩니다.
pattern[0] 또는 pattern[1]를 정확히 한 번만 추가할 수 있습니다. text 의 처음이나 끝에도 문자를 추가할 수 있습니다.

수정된 text의 하위 시퀀스로 발생할 수 있는 최대 횟수pattern를 반환합니다.

하위 시퀀스는 나머지 문자의 순서를 변경하지 않고 일부 문자를 삭제하거나 전혀 삭제하지 않음으로써 다른 문자열에서 파생될 수 있는 문자열입니다.

예 1:

입력: 텍스트 = "abdcdbc", 패턴 = "ac"
출력: 4
설명:
text[1]과 text[2] 사이에 pattern[0] = 'a'를 추가하면 "ab*adcdbc"가 됩니다. 이제 하위 시퀀스로 "ac"가 나타나는 횟수는 4입니다.
텍스트에 문자를 추가한 후 4개의 하위 시퀀스 "ac"가 있는 다른 문자열은 "aabdcdbc"및 "abdacdbc"입니다.
그러나 "abdcadbc", "abdccdbc"및 "abdcdbcc*"와 같은 문자열은 얻을 수 있지만 하위 시퀀스 "ac"가 3개뿐이므로 차선책입니다.
하나의 문자만 추가하면 4개 이상의 하위 시퀀스 "ac"를 얻을 수 없음을 알 수 있습니다.

예 2:

입력: 텍스트 = "aabb", 패턴 = "ab"
출력: 6
설명:
텍스트에서 얻을 수 있고 6개의 하위 시퀀스 "ab"가 있는 일부 문자열은 "aaabb", "aa*abb"및 "aabb*b"입니다.

제약:

text

1 <= text.length <= 105

pattern.length == 2 및 text는 영문 소문자로만 구성됩니다.

해결책:

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