3090. Maximum Length Substring With Two Occurrences

Problem Description

Given a string s, return the maximum length of a substring such that it contains at most two occurrences of each character.

Intuition

When tackling this problem, our goal is to find the longest substring within a given string s where no character appears more than twice. To efficiently solve this, a sliding window approach is quite effective.

We utilize two pointers to define the current window of characters we're examining, with these pointers helping us traverse through the string. Specifically, we advance one pointer to expand the window and check each character's count within the window. If any character in the window appears more than twice, we increment the other pointer to contract the window until the character count returns to a permissible level.

By maintaining an updated count of characters within the current window and adjusting the window boundaries as needed, we can efficiently calculate the maximum length of any substring meeting our criteria. The main strategy is optimizing the window size while ensuring the character count condition is satisfied.

Learn more about Sliding Window patterns.

Solution Approach

The solution approaches this problem using the "Two Pointers" technique, which is often used for solving problems involving subarrays or substrings in order to maintain a sliding window. Here's a detailed explanation of the implementation:

We initialize two pointers, i and j, to track the start and end of the current window, respectively. Additionally, a counter cnt is used to keep track of the number of occurrences of each character within the window.
As we iterate over the string with pointer j, each character c is added to the cnt, updating the count of that particular character.
If at any point, the count of c exceeds 2, we shift the i pointer to the right, effectively reducing the size of the window, until cnt[c] is less than or equal to 2. This ensures that every character in the window appears at most twice.
After adjusting the window, we update the maximum length of the valid substring encountered so far. This is done by calculating j - i + 1 and updating ans as max(ans, j - i + 1).
Finally, after iterating through the string, the answer ans, which represents the length of the longest valid substring, is returned.

The implementation efficiently adjusts the window and checks conditions in linear time, making it optimal for handling the problem constraints.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider the string s = "aabbcc". We are tasked to find the maximum length of a substring where no character appears more than twice. We'll employ the two pointers technique with a sliding window to solve this problem.

Initialize Pointers and Counter:
- Start with two pointers, i = 0 and j = 0, and initialize an empty dictionary cnt to keep track of character counts within the current window.
- Initialize ans = 0 to keep track of the maximum length of valid substrings we find.
Expand the Window with Pointer j:
- Move j from the start to the end of the string, examining each character. For every character c = s[j], increase its count in cnt, i.e., cnt[c] += 1.
Check and Adjust Window:
- After updating cnt, check if any character count exceeds 2.
- If cnt[s[j]] > 2, this violates our condition. Increment the start pointer i, and decrease cnt[s[i]] to reduce the window size until all characters have counts of at most 2.
Update Maximum Length:
- Calculate the current window size as j - i + 1 and update ans = max(ans, j - i + 1), ensuring we store the longest valid substring found so far.
Continue to End of String:
- Repeat steps 2-4 until pointer j has traversed the entire string.
Return Result:
- After finishing the iteration, ans holds the maximum length of a substring where no character appears more than twice.

In our example, s = "aabbcc", here's how it unfolds:

For j = 0, s[j] = "a", update cnt to {"a": 1}. The window [i, j] is [0, 0] and valid. Update ans = 1.
For j = 1, s[j] = "a", update cnt to {"a": 2}. The window [i, j] is [0, 1] and valid. Update ans = 2.
For j = 2, s[j] = "b", update cnt to {"a": 2, "b": 1}. The window [i, j] is [0, 2] and valid. Update ans = 3.
For j = 3, s[j] = "b", update cnt to {"a": 2, "b": 2}. The window [i, j] is [0, 3] and valid. Update ans = 4.
For j = 4, s[j] = "c", update cnt to {"a": 2, "b": 2, "c": 1}. The window [i, j] is [0, 4] and valid. Update ans = 5.
For j = 5, s[j] = "c", update cnt to {"a": 2, "b": 2, "c": 2}. The window [i, j] is [0, 5] and valid. Update ans = 6.

The answer for this example is 6, as the entire string meets the condition.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def maximumLengthSubstring(self, s: str) -> int:
5        # Initialize a Counter to track the frequency of characters in the current window
6        counter = Counter()
7        # Initialize variables to store the maximum length found and the start index of the window
8        max_length = start_index = 0
9      
10        # Iterate over each character in the string along with its index
11        for end_index, char in enumerate(s):
12            # Increment the count of the current character in the window
13            counter[char] += 1
14            # While there are more than 2 occurrences of the current character
15            while counter[char] > 2:
16                # Decrease the count of the character at start_index
17                counter[s[start_index]] -= 1
18                # Move the window start position to the right
19                start_index += 1
20            # Update the maximum length found so far
21            max_length = max(max_length, end_index - start_index + 1)
22      
23        # Return the maximum length of substring found
24        return max_length
25

1class Solution {
2    public int maximumLengthSubstring(String s) {
3        // Array to store the count of each character in the current window.
4        int[] charCount = new int[26];
5        // Variable to keep track of the maximum length of the valid substring.
6        int maxLength = 0;
7
8        // Two pointers to define the sliding window: i is the start, j is the end.
9        for (int start = 0, end = 0; end < s.length(); ++end) {
10            // Get index for the current character in the alphabet (0-based).
11            int charIndex = s.charAt(end) - 'a';
12            // Increment the count for the current character.
13            ++charCount[charIndex];
14
15            // If the count of the current character exceeds 2, shrink the window from the start.
16            while (charCount[charIndex] > 2) {
17                // Decrement the count of the character at the start of the window.
18                --charCount[s.charAt(start) - 'a'];
19                // Move start forward to shrink the window.
20                ++start;
21            }
22
23            // Update the maximum length of the substring found so far.
24            maxLength = Math.max(maxLength, end - start + 1);
25        }
26
27        // Return the maximum length of the substring where no character appears more than twice.
28        return maxLength;
29    }
30}
31

1#include <string>
2#include <algorithm>
3
4class Solution {
5public:
6    int maximumLengthSubstring(std::string s) {
7        int letterCount[26] = {}; // Array to count occurrences of each letter (a-z)
8        int result = 0; // Variable to store the maximum length of the substring found
9        int left = 0; // Pointer to the start of the window
10
11        // Traverse the string using a right pointer
12        for (int right = 0; right < s.length(); ++right) {
13            int index = s[right] - 'a'; // Calculate the index for the current letter
14            ++letterCount[index]; // Increment the count for this letter
15
16            // If any letter count is greater than 2, move the left pointer
17            while (letterCount[index] > 2) {
18                --letterCount[s[left] - 'a']; // Decrease the count of the leftmost letter
19                ++left; // Move the left pointer to the right
20            }
21
22            // Calculate the current window size and update the result
23            result = std::max(result, right - left + 1);
24        }
25      
26        return result;
27    }
28};
29

1// This function calculates the maximum length of a substring with each character appearing at most twice.
2function maximumLengthSubstring(s: string): number {
3    let ans = 0; // To store the maximum length of such a substring
4    const cnt: number[] = Array(26).fill(0); // Initialize an array to track the count of each letter in the substring
5
6    // Two pointers: i is the start, j is the end of the sliding window
7    for (let i = 0, j = 0; j < s.length; ++j) {
8        // Get the index of the current character in the alphabet (0 for 'a', ..., 25 for 'z')
9        const idx = s[j].charCodeAt(0) - 'a'.charCodeAt(0);
10      
11        // Increment the count of the character at the current position
12        ++cnt[idx];
13
14        // If the count of the current character exceeds 2, shift the start of the window
15        while (cnt[idx] > 2) {
16            // Decrease the count of the character at the start of the window
17            --cnt[s[i].charCodeAt(0) - 'a'.charCodeAt(0)];
18            // Move the start of the window to the right
19            i++;
20        }
21
22        // Update the maximum length found so far
23        ans = Math.max(ans, j - i + 1);
24    }
25
26    // Return the maximum length obtained
27    return ans;
28}
29

Time and Space Complexity

The time complexity of the provided code is O(n), where n is the length of the string s. This is because each character is processed at most twice, once when increasing the count and potentially when decreasing the count in the inner loop.

The space complexity is O(|Σ|), where Σ is the character set. In this problem, Σ = 26, representing the 26 lowercase English letters, making the space complexity effectively constant, or O(1).

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: