Maximize Number of Subsequences in a String

Medium
1234.

Maximize Number of Subsequences in a String

Maximize Number of Subsequences in a String is a medium coding problem on strings, greedy and prefix sum, asked in Amazon and Google interviews.

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^4
  • pattern.length == 2
  • text and pattern consist only of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} text
 * @param {string} pattern
 * @return {number}
 */
var maximumSubsequenceCount = function(text, pattern) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^4
  • pattern.length == 2
  • text and pattern consist only of lowercase English letters

Hints for Maximize Number of Subsequences in a String

  1. Hint 1

    First count the occurrences in text as it is: for every pattern[1], add how many pattern[0]s came before it.

  2. Hint 2

    Where is the best place for an extra pattern[0]? And for an extra pattern[1]?

  3. Hint 3

    A pattern[0] at the very front pairs with every pattern[1]; a pattern[1] at the very end pairs with every pattern[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

  1. Scan text once, keeping ca = number of pattern[0] seen so far and cb = number of pattern[1] seen.
  2. At each character, if it equals pattern[1] add ca to the running total (pairs it closes), then if it equals pattern[0] increase ca; count cb alongside.
  3. 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