2207. Maximize Number of Subsequences in a String
Problem Description
You are given a string text
which is indexed from 0
. You are also given another string pattern
, which is of length 2
and also indexed from 0
. Both strings contain only lowercase English letters. You have the option to add one character either pattern[0]
or pattern[1]
to any position in the text
string exactly once. This includes the possibility of adding the character at the start or the end of the text
. Your task is to figure out the maximum number of times the pattern
can be found as a subsequence in the new string after adding one character.
To clarify, a subsequence is a sequence that can be derived from another sequence by deleting some characters (or none) without altering the order of the remaining characters.
For example, given text = "ababc"
and pattern = "ab"
, if we add "a" to the text
to form "aababc", we can now see the subsequence "ab" occurs 4 times (indices 0-1, 0-3, 2-3, and 2-5).
Intuition
The intuition behind the solution lies in understanding what a subsequence is and how the addition of a character impacts the count of subsequences. The key insight is that by adding a character from the pattern
to the text
, we can increase the occurrences of that pattern
as a subsequence.
We can track the occurrences of pattern[0]
and the potential matches of the pattern
as we iterate through the text
. Each time we encounter the second character of the pattern
in the text (pattern[1]
), we know that any previous occurrences of pattern[0]
could form a new subsequence match with it. We keep a cumulative count of pattern[0]
's occurrences as we scan through the text
, adding to the answer whenever we see pattern[1]
.
Finally, we add the larger of the counts of pattern[0]
and pattern[1]
to ans
because we can insert one additional character pattern[0]
or pattern[1]
to the text (at the best place possible), which will create the most additional subsequences.
This approach allows us to efficiently calculate the maximum number of subsequence counts possible by traversing the string only once.
Learn more about Greedy and Prefix Sum patterns.
Solution Approach
The solution uses a two-pass approach with a counter to keep track of occurrences of characters from the pattern
.
- Initialize a variable
ans
to keep track of the number of subsequences ofpattern
found intext
. - Create a
Counter
object namedcnt
that will hold the frequency of each character we encounter intext
. - Iterate over each character
c
in thetext
string.- If the current character
c
is the same as the second character inpattern
(pattern[1]
), we incrementans
by the number of times the first character ofpattern
(pattern[0]
) has appeared so far. This is because each occurrence ofpattern[0]
beforepattern[1]
could form a new valid subsequence withpattern[1]
. - Update
cnt[c]
by incrementing it by1
to keep the count of each character.
- If the current character
- After the iteration is complete, add to
ans
the maximum frequency betweencnt[pattern[0]]
andcnt[pattern[1]]
. We can add one instance of eitherpattern[0]
orpattern[1]
anywhere intext
to maximize the subsequence count. Adding the character from the pattern with the highest frequency will yield the highest number of subsequences. - Return the final answer
ans
, which represents the maximum number of timespattern
can occur as a subsequence in the modifiedtext
.
Let's look at an example to better understand the approach:
text = "ababc"
,pattern = "ab"
- As we iterate through
text
, we count occurrences of 'a' and 'b'. - When we reach the first 'b' at index 1,
ans
is increased by the count of 'a' seen so far, which is 1 (cnt['a'] = 1
). - As we continue, every time we encounter 'b', we add the count of 'a's seen so far to
ans
. - After the loop, we can add one more 'a' or 'b' (choosing 'a' is better in this case, as
cnt['a']
>cnt['b']
), addingcnt['a']
(which is 2) toans
. - Finally,
ans
becomes4
, which is the maximum subsequence count after the addition.
The use of a Counter allows us to efficiently keep track of character frequencies, and the single pass approach with an additional step minimizes the time complexity, resulting in an elegant and effective solution.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's apply the solution approach to a small example where text = "bbaca"
and pattern = "ba"
.
- We initialize
ans = 0
because initially, we haven't found any subsequences of thepattern
yet. - We create a
Counter
objectcnt
to keep track of occurrences of characters intext
. It is initially empty. - We start iterating through the
text
:- We encounter the first 'b'. It's not the second character of
pattern
, so we just updatecnt['b']
to 1. - We encounter the second 'b'. Again, it's not
pattern[1]
, so we updatecnt['b']
to 2. - We encounter 'a', and since it is
pattern[0]
, we updatecnt['a']
to 1 but do not alterans
since 'a' is not the second character in thepattern
. - Next, we encounter 'c'. It's neither
pattern[0]
norpattern[1]
, so we continue. - Finally, we encounter another 'a'. We update
cnt['a']
to 2.
- We encounter the first 'b'. It's not the second character of
- As we continue scanning, we find the last character 'b', which is
pattern[1]
. Now we add toans
the count of 'a' seen so far because 'a' followed by this 'b' can form another subsequence "ba". Theans
is incremented bycnt['a']
, which is 2. So now,ans = 2
. - After the iteration is over, we look at the counts of 'b' and 'a' in
cnt
. We havecnt['b'] = 2
andcnt['a'] = 2
. We can add one more character totext
. To maximize the subsequences, we should choose to add the character with the maximum count. - In this case, both
cnt['b']
andcnt['a']
are the same, so we can choose either. Let's choose to add another 'a'. - By adding an 'a', we will be able to create new subsequences "ba" with all existing 'b's. Therefore, we add
cnt['b']
toans
, which results in an additional 2 subsequences.
So, the final answer ans
is now 2 + 2 = 4
, which represents the maximum number of times pattern = "ba"
can occur as a subsequence in the modified text
after adding one extra 'a'.
This walkthrough demonstrates the process of calculating the number of subsequences of a given pattern in a text by iteratively counting characters, leveraging the subsequence definition, and maximizing the outcome by intelligently adding a character to the text based on the counts obtained.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def maximumSubsequenceCount(self, text: str, pattern: str) -> int:
5 # Initialize the total count of subsequences found
6 total_subsequence_count = 0
7
8 # Create a counter to store the frequency of characters encountered
9 character_frequency = Counter()
10
11 # Iterate through all characters in the text
12 for character in text:
13 # If the current character matches the second character of the given pattern
14 if character == pattern[1]:
15 # Increment the subsequence count by the frequency of the first pattern character seen so far
16 total_subsequence_count += character_frequency[pattern[0]]
17
18 # Increment the frequency of the current character
19 character_frequency[character] += 1
20
21 # Add the maximum frequency between the first and second pattern characters
22 # This accounts for the option to add a pattern character before or after the text
23 total_subsequence_count += max(character_frequency[pattern[0]], character_frequency[pattern[1]])
24
25 # Return the total count of pattern subsequences that can be found or added in the text
26 return total_subsequence_count
27
1public class Solution {
2
3 /**
4 * Calculates the maximum number of times a given pattern appears as a subsequence
5 * in the given text by potentially adding either character of the pattern at the beginning or end.
6 *
7 * @param text The input text in which subsequences are to be counted.
8 * @param pattern The pattern consisting of two characters to be looked for as a subsequence.
9 * @return The maximum number of times the pattern can occur as a subsequence.
10 */
11 public long maximumSubsequenceCount(String text, String pattern) {
12 // Array to track the frequency of each character in the text
13 int[] charCount = new int[26];
14
15 // Extract the two characters from the pattern
16 char firstPatternChar = pattern.charAt(0);
17 char secondPatternChar = pattern.charAt(1);
18
19 // This will hold the number of times the pattern occurs as a subsequence
20 long totalCount = 0;
21
22 // Iterate over each character in the text
23 for (char currentChar : text.toCharArray()) {
24 // If the current char matches the second char of the pattern,
25 // increment the pattern occurrence count by the number of occurrences
26 // of the first pattern character that have been seen so far.
27 if (currentChar == secondPatternChar) {
28 totalCount += charCount[firstPatternChar - 'a'];
29 }
30 // Update the count of the current character in our tracking array.
31 charCount[currentChar - 'a']++;
32 }
33
34 // Increase the totalCount by the max frequency of appearing of either of the pattern characters.
35 // This is because we can add one character (either the first or the second in the pattern)
36 // to the start or the end of the text to increase the count of subsequences by that amount.
37 totalCount += Math.max(charCount[firstPatternChar - 'a'], charCount[secondPatternChar - 'a']);
38
39 // Return the total number of times the pattern can occur as a subsequence.
40 return totalCount;
41 }
42}
43
1class Solution {
2public:
3 long long maximumSubsequenceCount(string text, string pattern) {
4 long long totalCount = 0; // This will hold the total count of desired subsequences
5 char firstPatternChar = pattern[0]; // The first character in the pattern
6 char secondPatternChar = pattern[1]; // The second character in the pattern
7
8 // Initialize a count array for all letters, assuming English lower-case letters only
9 vector<int> charCount(26, 0);
10
11 // Iterate over each character in the text string
12 for (char& currentChar : text) {
13 // If the current char is the second in the pattern, add the count of the first pattern char seen so far
14 if (currentChar == secondPatternChar) {
15 totalCount += charCount[firstPatternChar - 'a'];
16 }
17 // Increment the count of the currentChar in the charCount vector
18 charCount[currentChar - 'a']++;
19 }
20
21 // We can add either one of the pattern characters to either the beginning or the end of the string.
22 // We choose the character that gives us more subsequences.
23 // So, add the max between the occurrences of the two pattern characters to totalCount.
24 totalCount += max(charCount[firstPatternChar - 'a'], charCount[secondPatternChar - 'a']);
25
26 return totalCount; // Return the final total count of subsequences.
27 }
28};
29
1// Function to calculate the maximum number of subsequences with a given pattern in a text
2function maximumSubsequenceCount(text: string, pattern: string): number {
3 let totalCount = 0; // This will hold the total count of desired subsequences
4 let firstPatternChar = pattern[0]; // The first character in the pattern
5 let secondPatternChar = pattern[1]; // The second character in the pattern
6
7 // Initialize a count array for all letters. In TypeScript, a Map is often more appropriate.
8 let charCount: Map<string, number> = new Map<string, number>();
9
10 // Iterate over each character in the text string
11 for (let currentChar of text) {
12 // If the current char is the second in the pattern, add the count of the first pattern char seen so far
13 if (currentChar === secondPatternChar) {
14 totalCount += (charCount.get(firstPatternChar) || 0);
15 }
16 // Increment the count of the currentChar in the charCount map
17 charCount.set(currentChar, (charCount.get(currentChar) || 0) + 1);
18 }
19
20 // We can add either one of the pattern characters to either the beginning or the end of the string.
21 // We choose the character that gives us more subsequences.
22 // So, add the maximum between the occurrences of the two pattern characters to totalCount.
23 totalCount += Math.max(charCount.get(firstPatternChar) || 0, charCount.get(secondPatternChar) || 0);
24
25 return totalCount; // Return the final total count of subsequences.
26}
27
28// Usage of the function
29const result = maximumSubsequenceCount("exampletext", "et");
30console.log(result); // This would print the result of the function call to the console
31
Time and Space Complexity
The given Python code calculates the number of times a certain pattern of two characters can be inserted into a text such that the subsequence count of that pattern is maximized.
Time Complexity
The time complexity of the function is determined by a single pass over the text string text
, which has length n
. During this pass, for each character c
in text
, the code updates the Counter
object cnt
and in some cases increments the answer ans
.
Accessing and updating the count in Counter
for each character is generally O(1) complexity assuming a good hash function (as Counter
is a type of dict
in Python, and dictionary access is generally considered constant time).
The increment of ans
based on cnt[pattern[0]]
also occurs in constant time.
Therefore, because we have a single pass over the text
with constant-time operations within the loop, the overall time complexity of the function is O(n)
, where n
is the length of the input string text
.
Space Complexity
The space complexity is determined by the additional space used which is mainly the Counter
object cnt
. In the worst case, cnt
could store a count for every unique character in text
. The number of unique characters in text
could be up to the size of the character set but is typically much smaller.
If we only consider the length of text
, the space complexity would be O(u)
where u
is the number of unique characters in the text
, which is less than or equal to n
.
However, since the space taken up by cnt
does not scale with the size of the input text
, but rather with the number of unique characters, it might also be fair to consider it O(1)
space, under the assumption that the character set size is fixed and not very large (e.g., ASCII characters).
So, the space complexity is either O(u)
or O(1)
, depending on whether you count the fixed size of the character set as constant or not.
Learn more about how to find time and space complexity quickly using problem constraints.
What are the most two important steps in writing a depth first search function? (Select 2)
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we