Maximize Number of Subsequences in a String

Maximize Number of Subsequences in a String - 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. 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.

Input & Output

Example 1 — Basic Case

$ Input: text = "abdcdbc", pattern = "ac"

› Output: 4

💡 Note: Adding 'a' at the start gives "aabdcdbc". We can form "ac" subsequences: positions (0,4), (0,6), (1,4), (1,6) = 4 total.

Example 2 — Same Characters

$ Input: text = "aabb", pattern = "ab"

› Output: 6

💡 Note: Adding 'a' at start gives "aaabb" with 3 'a's and 2 'b's. Total subsequences = 3 × 2 = 6.

Example 3 — Identical Pattern

$ Input: text = "aa", pattern = "aa"

› Output: 3

💡 Note: Adding another 'a' gives 3 'a's total. Number of ways to choose 2 from 3 = C(3,2) = 3.

Constraints

1 ≤ text.length ≤ 10⁵
pattern.length == 2
text and pattern consist of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Text string and 2-character pattern

Process

Add one pattern character optimally

Output

Maximum possible subsequence count

Key Takeaway

🎯 Key Insight: Adding pattern[0] at start or pattern[1] at end usually gives optimal results

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that adding pattern[0] at the beginning or pattern[1] at the end typically gives optimal results. Best approach uses greedy counting to calculate benefits of each insertion without trying all positions. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy with Prefix Counting	O(n)	O(1)	Count characters and determine optimal insertion strategy
Brute Force - Try All Positions	O(n³)	O(n)	Try inserting each character at every position and count subsequences

Greedy with Prefix Counting — Algorithm Steps

Count existing subsequences in original text
Calculate benefit of adding pattern[0] at start
Calculate benefit of adding pattern[1] at end
Return original count plus maximum benefit

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Original

Count existing pattern subsequences

Calculate Benefits

Determine gain from each insertion

Choose Optimal

Pick insertion with maximum benefit

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

long long solution(char* text, char* pattern) {
    char first = pattern[0];
    char second = pattern[1];
    
    if (first == second) {
        // Special case: both characters are the same
        long long count = 0;
        for (int i = 0; text[i]; i++) {
            if (text[i] == first) count++;
        }
        return (count + 1) * (count + 2) / 2;
    }
    
    // Count existing subsequences
    long long countFirst = 0;
    long long totalSubsequences = 0;
    for (int i = 0; text[i]; i++) {
        if (text[i] == first) {
            countFirst++;
        } else if (text[i] == second) {
            totalSubsequences += countFirst;
        }
    }
    
    // Calculate benefits of each insertion
    long long countPattern0 = 0;
    long long countPattern1 = 0;
    for (int i = 0; text[i]; i++) {
        if (text[i] == first) countPattern0++;
        if (text[i] == second) countPattern1++;
    }
    
    // Benefit of adding pattern[0] at start
    long long benefitAddFirst = countPattern1;
    
    // Benefit of adding pattern[1] at end
    long long benefitAddSecond = countPattern0;
    
    long long maxBenefit = (benefitAddFirst > benefitAddSecond) ? benefitAddFirst : benefitAddSecond;
    
    return totalSubsequences + maxBenefit;
}

int main() {
    char text[100001], pattern[3];
    fgets(text, sizeof(text), stdin);
    fgets(pattern, sizeof(pattern), stdin);
    text[strcspn(text, "\n")] = 0;
    pattern[strcspn(pattern, "\n")] = 0;
    printf("%lld\n", solution(text, pattern));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through text to count characters and calculate benefits

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for counting

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

823 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy with Prefix Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler