We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximize Number of Subsequences in a String

Number: 2309

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given a 0-indexed string text and a 2-character string pattern, you are allowed to insert exactly one character into text. The inserted character can either be pattern[0] or pattern[1] and can be placed anywhere (including at the beginning or end). The goal is to maximize the number of times pattern occurs as a subsequence in the modified text. A subsequence is a sequence that can be derived from the text by deleting some (or no) characters without changing the order of the remaining characters.

Key Insights

  • There are two cases depending on whether pattern[0] equals pattern[1].
  • When pattern[0] != pattern[1]:
    • Count the base occurrence of the subsequence "xy" (where x = pattern[0] and y = pattern[1]) in text.
    • Inserting an extra x at the beginning lets it pair with all y’s, adding count(y) new subsequences.
    • Alternatively, inserting an extra y at the end allows it to pair with all x’s, adding count(x) new subsequences.
    • The answer is the base count plus the maximum of count(x) and count(y).
  • When pattern[0] == pattern[1]:
    • The subsequence is a repeated character, e.g., "aa". The count of subsequences is given by the number of pairs that can be formed, which is C(n, 2) = n*(n-1)/2 for frequency n.
    • Inserting one more instance increases the frequency to n+1, resulting in (n+1)*n/2 subsequences.

Space and Time Complexity

Time Complexity: O(n), where n is the length of text, as we scan through the text to count characters and subsequences. Space Complexity: O(1), constant extra space is used.

Solution

This problem is tackled by separately handling the cases where the two characters in the pattern are equal or distinct.

For the case of distinct characters, we first compute the number of "xy" subsequences (with x = pattern[0] and y = pattern[1]) in the given text using a single pass. Then, we determine how many extra subsequences we can get by inserting either an extra x at an optimal position (preferably at the start so it pairs with every y) or an extra y at the end (so that it pairs with every x). The maximum added subsequences from the insertion equals max(count(x), count(y)), which we add to the base subsequence count.

For the case when the pattern’s characters are identical (say "aa"), the solution involves a combinatorial calculation. Count the occurrences of the repeated character in text and compute how many pairs there are. By inserting one additional character, the total number of such pairs becomes (frequency + 1) choose 2.

Data structures used include a few counters and variables; the primary algorithm is based on a single traversal (or linear scan) of the input text.

Code Solutions

# Python solution for "Maximize Number of Subsequences in a String"

def maximumSubsequenceCount(text, pattern):
    # If both characters in pattern are the same, use combinatorial formula.
    if pattern[0] == pattern[1]:
        char_count = text.count(pattern[0])
        # After insertion, total count becomes char_count + 1; 
        # the subsequences count is (n+1)*n/2.
        return (char_count + 1) * char_count // 2
    
    # For pattern[0] != pattern[1]
    count_x = 0         # Number of pattern[0] seen so far.
    base_count = 0      # Base subsequence count "xy" in text.
    
    # Traverse text to calculate the number of subsequences in the original text.
    for ch in text:
        if ch == pattern[0]:
            count_x += 1
        elif ch == pattern[1]:
            base_count += count_x
    
    # Count total occurrences of pattern[0] and pattern[1] in text.
    total_x = text.count(pattern[0])
    total_y = text.count(pattern[1])
    
    # Inserting pattern[0] at the beginning (or anywhere before all y's)
    # will pair with all occurrences of pattern[1].
    # Inserting pattern[1] at the end to pair with all occurrences of pattern[0].
    additional = max(total_y, total_x)
    
    return base_count + additional

# Example usage:
print(maximumSubsequenceCount("abdcdbc", "ac"))  # Expected output: 4
print(maximumSubsequenceCount("aabb", "ab"))      # Expected output: 6
← Back to All Questions