2207. Maximize Number of Subsequences in a String

📝 Problem Details

• Title: 2207. Maximize Number of Subsequences in a String
• Link: https://leetcode.com/problems/maximize-number-of-subsequences-in-a-string/
• Difficulty: Medium
• Tags/Categories: Strings Greedy Prefix-Sum

🔍 Problem Understanding

1. Subsequences:

   • a subsequence of a string is a sequence derived by deleting some or no characters of the string without changing the order of the remaining characters
   • e.g. s = abd, the subsequences include a b c ab ac bc abc

2. Task:

   • you are given string text and 2 characters inside string pattern (lets call them x and y)
   • the goal is the maximize the number of xy subsequences (where x comes before y in the string) by inserting one additional character (x or y) into the string

3. Rules:

   • you can only insert one character at a time: either x or y
   • the insertion can be done at any position in the string (even at the beginning or end )

4. Objective:

   • determine the maximum number of xy subsequences you can obtain after the insertion

💭What Were My Initial Thoughts?

~

🤔What Did I Struggle With?

question was hard to understand 

💡 Explanation of Solution

- **Track Existing Subsequence Counts**:
    - Use `cnt1` to count occurrences of `pattern[0]` as we iterate through the string.
    - Use `cnt2` to count occurrences of `pattern[1]`.

- **Update Subsequence Count**:    
    - If the current character is `pattern[0]`, increment `cnt1`.
    - If the current character is `pattern[1]`, it forms subsequences with all previous `pattern[0]` characters, so increment `cnt2` and add `cnt1` to the result.

- **Consider Adding a New Character**:    
    - If you add `pattern[0]`, place it at the beginning. This forms additional subsequences with every `pattern[1]`, so add `cnt2` to the result.
    - If you add `pattern[1]`, place it at the end. This forms additional subsequences with every `pattern[0]`, so add `cnt1` to the result.

- **Output the Maximum**:
    - Return the maximum of the existing subsequences and the two cases of adding a character.

⌛ Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    long long maximumSubsequenceCount(string text, string pattern) {
        long long count1 = 0;
        long long count2 = 0;
        long long result = 0;
 
        // calculate the current number of pattern subsequences
        for(char c : text) {
            if(c == pattern[1]) {
 
                // Each `pattern[1]` pairs with all previous `pattern[0]`
                result += count1;
                count2++; 
            }
            if(c == pattern[0]) {
                count1++;
            }
        }
 
        // consider adding one character
        long long addPattern0 = result + count2; // add pattern[0] at the start
        long long addPattern1 = result + count1; // add pattern[1] at the end
 
        return max({result, addPattern0, addPattern1});
    }
};