MediumNo. 2207
Maximize Number of Subsequences in a String — LeetCode 2207 Python Solution
- Pattern
- Prefix Sum
- Topics
- Greedy, String, Prefix Sum
- Reading time
- 2 min
- Source
- leetcode.com
The problem
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.
Example
- 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.
Python solution
class Solution:
def maximumSubsequenceCount(self, text: str, pattern: str) -> int:
ans = x = y = 0
for c in text:
if c == pattern[1]:
y += 1
ans += x
if c == pattern[0]:
x += 1
ans += max(x, y)
return ansComplexity
- Time
- O(n)where n is the length of the string text
- Space · auxiliary
- O(1)
Pattern: Prefix Sum
Precompute running totals once so any range query becomes a single subtraction. LeetCode 2207. Maximize Number of Subsequences in a String is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.
The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0179 | Largest Number | Medium |
| 0316 | Remove Duplicate Letters | Medium |
| 0402 | Remove K Digits | Medium |
| 0420 | Strong Password Checker | Hard |
| 0649 | Dota2 Senate | Medium |
| 0680 | Valid Palindrome II | Easy |
Frequently asked questions
- How hard is LeetCode 2207. Maximize Number of Subsequences in a String?
LeetCode 2207. Maximize Number of Subsequences in a String is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2207. Maximize Number of Subsequences in a String?
The Python solution on this page runs in O(n), where n is the length of the string \textit{text}.
- What is the space complexity of LeetCode 2207. Maximize Number of Subsequences in a String?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 2207. Maximize Number of Subsequences in a String cover?
LeetCode 2207. Maximize Number of Subsequences in a String is tagged Greedy, String and Prefix Sum on LeetCode.