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
andpattern
consist only of lowercase English letters.
Solutions
Solution 1: Traversal + Counting
We can use two variables $x$ and $y$ to record the current counts of $\textit{pattern}[0]$ and $\textit{pattern}[1]$ in the string, respectively.
Then, traverse the string $\textit{text}$. For the current character $c$:
- If $c$ equals $\textit{pattern}[1]$, increment $y$ by one. At this point, all previously encountered $\textit{pattern}[0]$ can form a $\textit{pattern}$ subsequence with the current $c$, so add $x$ to the answer.
- If $c$ equals $\textit{pattern}[0]$, increment $x$ by one.
After the traversal, since we can insert one character, if we add $\textit{pattern}[0]$ at the beginning of the string, we can get $y$ $\textit{pattern}$ subsequences. If we add $\textit{pattern}[1]$ at the end of the string, we can get $x$ $\textit{pattern}$ subsequences. Therefore, we add the larger value of $x$ and $y$ to the answer.
The time complexity is $O(n)$, where $n$ is the length of the string $\textit{text}$. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|