Problem Description

You have a string text and a pattern string pattern that contains exactly 2 characters (both strings contain only lowercase English letters and are 0-indexed).

Your task is to:

1. Add exactly one character to text - you can choose to add either pattern[0] or pattern[1]
2. You can add this character anywhere in text (including at the beginning or end)
3. Find the maximum number of times pattern appears as a subsequence in the modified text

A subsequence means you can form the pattern by selecting characters from the text in order (but not necessarily consecutive). For example, if pattern = "ab", then in the text "aabb", the pattern appears 4 times as a subsequence (we can choose the first 'a' with either 'b', or the second 'a' with either 'b').

The goal is to strategically place one additional character to maximize the count of pattern subsequences in the resulting string.

For example:

• If text = "abdcdbc" and pattern = "ac"
• We could add 'a' at the beginning to get "aabdcdbc", or add 'c' at the end to get "abdcdbcc"
• We need to determine which placement gives us the most "ac" subsequences

Intuition

To understand how to maximize subsequences, let's think about how subsequences of pattern are formed. For a pattern like "ab", each occurrence of 'a' can pair with any 'b' that comes after it. So if we have 3 'a's followed by 2 'b's, we get 3 × 2 = 6 subsequences.

The key insight is that when we traverse the string from left to right:

• Each time we encounter pattern[1], it can form a subsequence with every pattern[0] we've seen before it
• We need to keep track of how many pattern[0] characters we've seen so far

As we scan through text, we maintain two counters:

• x: count of pattern[0] seen so far
• y: count of pattern[1] seen so far

When we hit a pattern[1], we add x to our answer because this new pattern[1] creates x new subsequences (one with each previously seen pattern[0]).

Now for the strategic placement of our one additional character:

• If we add pattern[0] at the beginning, it can pair with all existing pattern[1] characters in the text, giving us y additional subsequences
• If we add pattern[1] at the end, it can pair with all existing pattern[0] characters in the text, giving us x additional subsequences

Therefore, the optimal strategy is to add whichever character would give us more additional subsequences - that's max(x, y).

This greedy approach works because adding at the extremes (beginning for pattern[0] or end for pattern[1]) ensures maximum pairing opportunities without disrupting existing subsequence counts.

Learn more about Greedy and Prefix Sum patterns.

Solution Approach

We implement a single-pass traversal algorithm with counting to solve this problem efficiently.

Algorithm Steps:

1. Initialize counters: Set up three variables:

   • ans = 0: stores the total count of pattern subsequences
   • x = 0: counts occurrences of pattern[0]
   • y = 0: counts occurrences of pattern[1]

2. Traverse the string: For each character c in text:

   • If c == pattern[1]:
     • Increment y by 1 (we found another pattern[1])
     • Add x to ans (this pattern[1] forms subsequences with all previous pattern[0]s)
   • If c == pattern[0]:
     • Increment x by 1 (we found another pattern[0])

3. Handle the additional character: After traversal, add max(x, y) to the answer:

   • Adding pattern[0] at the beginning would create y new subsequences
   • Adding pattern[1] at the end would create x new subsequences
   • We choose the option that maximizes our count

Why this order matters:

• We check for pattern[1] first and update the answer before checking pattern[0]
• This handles the edge case where pattern[0] == pattern[1] correctly
• When both characters are the same, each character acts as both the first and second element of the pattern

Time Complexity: O(n) where n is the length of text - we make a single pass through the string

Space Complexity: O(1) - we only use a constant amount of extra space for counters

The beauty of this solution lies in its simplicity - by maintaining running counts and understanding how subsequences are formed, we can calculate the result in a single pass without needing to actually modify the string or try different insertion positions.

Example Walkthrough

Let's walk through a concrete example with text = "abad" and pattern = "ab".

Step 1: Initialize counters

• ans = 0 (total subsequences count)
• x = 0 (count of 'a')
• y = 0 (count of 'b')

Step 2: Traverse the string character by character

Processing index 0: c = 'a'

• 'a' == pattern[0], so increment x
• x = 1, y = 0, ans = 0

Processing index 1: c = 'b'

• 'b' == pattern[1], so:
  • Increment y: y = 1
  • Add x to ans: ans = 0 + 1 = 1 (this 'b' forms 1 subsequence with the previous 'a')
• x = 1, y = 1, ans = 1

Processing index 2: c = 'a'

• 'a' == pattern[0], so increment x
• x = 2, y = 1, ans = 1

Processing index 3: c = 'd'

• 'd' is neither pattern[0] nor pattern[1], so no changes
• x = 2, y = 1, ans = 1

Step 3: Determine optimal character placement

After traversal: x = 2 (we have 2 'a's) and y = 1 (we have 1 'b')

Now we decide which character to add:

• If we add 'a' at the beginning → "aabad": This new 'a' can pair with the existing 1 'b', creating 1 additional subsequence
• If we add 'b' at the end → "abadb": This new 'b' can pair with the existing 2 'a's, creating 2 additional subsequences

Since max(x, y) = max(2, 1) = 2, we add 2 to our answer.

Final Result: ans = 1 + 2 = 3

This means the maximum number of "ab" subsequences we can achieve is 3 (by adding 'b' at the end to get "abadb", which contains the subsequences: a₁b₁, a₁b₂, and a₂b₂).

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string text. The algorithm iterates through the string exactly once using a single for loop, performing constant-time operations (comparisons, additions, and variable updates) for each character.

The space complexity is O(1). The algorithm uses only a fixed number of variables (ans, x, y, and the loop variable c) regardless of the input size. No additional data structures that scale with the input are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Order of Character Checking

The Problem: Many developers instinctively check for pattern[0] first, then pattern[1]. This seems logical but fails when pattern[0] == pattern[1] (e.g., pattern = "aa").

Incorrect Implementation:

for char in text:
    if char == pattern[0]:  # Checking pattern[0] first
        first_char_count += 1
    if char == pattern[1]:  # Then checking pattern[1]
        second_char_count += 1
        total_subsequences += first_char_count

Why It Fails: When both pattern characters are the same (like "aa"), checking pattern[0] first means we increment first_char_count before adding it to total_subsequences. This causes us to count a character pairing with itself in the same position, which is invalid for a subsequence.

The Solution: Always check pattern[1] first and update the answer, then check pattern[0]:

for char in text:
    if char == pattern[1]:  # Check pattern[1] FIRST
        second_char_count += 1
        total_subsequences += first_char_count  # Use old count
    if char == pattern[0]:  # Then update pattern[0] count
        first_char_count += 1

Pitfall 2: Misunderstanding the Insertion Strategy

The Problem: Some solutions try to iterate through all possible insertion positions to find the optimal placement, leading to O(n²) complexity.

Incorrect Approach:

max_count = 0
for i in range(len(text) + 1):
    # Try inserting at position i
    modified = text[:i] + pattern[0] + text[i:]
    count = count_subsequences(modified, pattern)
    max_count = max(max_count, count)
    # Repeat for pattern[1]...

Why It's Inefficient: There are only two optimal choices: add pattern[0] at the beginning or add pattern[1] at the end. Any other position would yield fewer subsequences.

The Solution: Recognize that:

• Adding pattern[0] at the beginning creates subsequences with all existing pattern[1] characters
• Adding pattern[1] at the end creates subsequences with all existing pattern[0] characters
• Simply take the maximum of these two options: max(first_char_count, second_char_count)

Pitfall 3: Using 'elif' Instead of Separate 'if' Statements

The Problem: Using elif prevents counting when pattern[0] == pattern[1].

Incorrect Implementation:

for char in text:
    if char == pattern[1]:
        second_char_count += 1
        total_subsequences += first_char_count
    elif char == pattern[0]:  # Wrong! Should be 'if'
        first_char_count += 1

Why It Fails: When pattern = "aa" and we encounter an 'a', we need to execute both blocks - the character acts as both the first and second element of the pattern. Using elif skips the second block.

The Solution: Use two separate if statements to ensure both conditions are checked independently:

for char in text:
    if char == pattern[1]:
        # Handle as second character
    if char == pattern[0]:  # Separate 'if', not 'elif'
        # Handle as first character