Maximize Number of Subsequences in a String — Solution
Maximize Number of Subsequences in a String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximize Number of Subsequences in a String is a medium coding problem on strings, greedy and prefix sum, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Strings, Greedy, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string text and a string pattern of length 2, both lowercase.
Insert exactly one character into text — either pattern[0] or pattern[1] — at any position (including the very beginning or end).
Return the maximum number of times pattern can then occur in the new string as a subsequence: the number of index pairs i < j with newText[i] = pattern[0] and newText[j] = pattern[1].
The length bound below is tightened from the original problem so that the answer always fits in a 32-bit signed integer.
Example 1
Input: text = "kakao", pattern = "ko"
Output: 4
Explanation: Appending an `o` gives `"kakaoo"`: each of the two `o`s follows both `k`s.
Example 2
Input: text = "aabb", pattern = "ab"
Output: 6
Example 3
Input: text = "zzz", pattern = "zz"
Output: 6
Explanation: Four `z`s contain 4 × 3 / 2 = 6 ordered pairs.
Constraints
1 <= text.length <= 5 * 10^4pattern.length == 2text and pattern consist only of lowercase English letters
Hints for Maximize Number of Subsequences in a String
Hint 1
First count the occurrences in
textas it is: for everypattern[1], add how manypattern[0]s came before it.Hint 2
Where is the best place for an extra
pattern[0]? And for an extrapattern[1]?Hint 3
A
pattern[0]at the very front pairs with everypattern[1]; apattern[1]at the very end pairs with everypattern[0]. Add the larger of the two counts.
How to solve Maximize Number of Subsequences in a String
The inserted character only adds the pairs it takes part in. Put pattern[0] at the front or pattern[1] at the back, whichever pairs with more existing characters.
Approach
- Scan
textonce, keepingca= number ofpattern[0]seen so far andcb= number ofpattern[1]seen. - At each character, if it equals
pattern[1]addcato the running total (pairs it closes), then if it equalspattern[0]increaseca; countcbalongside. - Return
total + max(ca, cb).
Why it works
Inserting a character never destroys existing pairs; it only adds pairs that use it. An inserted pattern[0] forms a pair with every pattern[1] to its right, which is maximised at the front (cb pairs). An inserted pattern[1] pairs with every pattern[0] to its left, maximised at the end (ca pairs). When the two pattern letters are equal the same logic gives ca = cb, and checking pattern[1] before incrementing ca makes a character never pair with itself.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- When
pattern[0] == pattern[1], update the total before incrementing the count, or each character pairs with itself. - In the original constraints (n up to 10^5) the answer needs 64 bits; accumulate in a wide type.
- Trying every insertion point is O(n²) and unnecessary.
Reference solution
Python
def maximumSubsequenceCount(text: str, pattern: str) -> int:
a, b = pattern[0], pattern[1]
ca = cb = total = 0
for ch in text:
if ch == b:
total += ca
cb += 1
if ch == a:
ca += 1
return total + max(ca, cb)Java
public static int maximumSubsequenceCount(String text, String pattern) {
char a = pattern.charAt(0), b = pattern.charAt(1);
long ca = 0, cb = 0, total = 0;
for (int i = 0; i < text.length(); i++) {
char ch = text.charAt(i);
if (ch == b) { total += ca; cb++; }
if (ch == a) ca++;
}
return (int) (total + Math.max(ca, cb));
}C++
int maximumSubsequenceCount(string text, string pattern) {
char a = pattern[0], b = pattern[1];
long long ca = 0, cb = 0, total = 0;
for (char ch : text) {
if (ch == b) { total += ca; cb++; }
if (ch == a) ca++;
}
return (int)(total + max(ca, cb));
}JavaScript
var maximumSubsequenceCount = function(text, pattern) {
var a = pattern[0], b = pattern[1];
var ca = 0, cb = 0, total = 0;
for (var i = 0; i < text.length; i++) {
var ch = text[i];
if (ch === b) { total += ca; cb++; }
if (ch === a) ca++;
}
return total + Math.max(ca, cb);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Greedy Algorithms