Maximum Length Substring With Two Occurrences
EasyPrompt
s, return the maximum length of a substring such that it contains at most two occurrences of each character.
Example 1:
Input: s = "bcbbbcba"
Output: 4
Explanation:
The following substring has a length of 4 and contains at most two occurrences of each character:"bcbbbcba".Example 2:
Input: s = "aaaa"
Output: 2
Explanation:
The following substring has a length of 2 and contains at most two occurrences of each character:"aaaa".
Constraints:
2 <= s.length <= 100sconsists only of lowercase English letters.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach systematically checks every possible substring of the input string s. For each substring, it verifies if it meets the condition: containing at most two occurrences of each character. It keeps track of the length of the longest valid substring found.
Algorithm
- Initialize
maxLength = 0. - Iterate through the string with an index
ifrom0ton-1to define the start of the substring. - Inside this loop, create a frequency map
counts(e.g., an integer array of size 26 for lowercase English letters). - Start a nested loop with an index
jfromiton-1to define the end of the substring. - In the inner loop, get the character
c = s.charAt(j)and increment its count in thecountsmap. - Check if the count of
chas become greater than 2. - If
counts[c - 'a'] > 2, the current substrings.substring(i, j + 1)and any further extensions fromiare invalid. Break the inner loop. - If the count is valid (<= 2), update the maximum length:
maxLength = Math.max(maxLength, j - i + 1). - After the loops complete, return
maxLength.
Walkthrough
The algorithm uses two nested loops to generate all substrings. The outer loop, with index i, fixes the starting point of the substring. The inner loop, with index j, extends the substring to the right, one character at a time.
For each starting point i, a new frequency map (an array of size 26) is initialized to count character occurrences for substrings starting at i. As the inner loop progresses, we add s.charAt(j) to the current substring and update its frequency. We then check if this character's count has exceeded 2. If it has, the substring s.substring(i, j + 1) is invalid. Since any longer substring starting at i will also be invalid, we can break the inner loop and proceed to the next starting position i + 1.
If the character count is valid (i.e., less than or equal to 2), the current substring s.substring(i, j + 1) is valid, and we update our maxLength with its length if it's the largest seen so far.
class Solution { public int maximumLengthSubstring(String s) { int maxLength = 0; int n = s.length(); if (n == 0) { return 0; } for (int i = 0; i < n; i++) { int[] counts = new int[26]; for (int j = i; j < n; j++) { char c = s.charAt(j); counts[c - 'a']++; if (counts[c - 'a'] > 2) { // The substring from i to j is invalid, so any longer substring starting at i will also be invalid. break; } // The substring from i to j is valid. maxLength = Math.max(maxLength, j - i + 1); } } return maxLength; }}Complexity
Time
O(n^2), where n is the length of the string `s`. The nested loops iterate through approximately n^2/2 substrings, and the operations inside the inner loop take constant time.
Space
O(1) or O(k), where k is the number of unique characters in the alphabet (26 in this case). A new frequency map is created for each starting position `i`, but its size is constant.
Trade-offs
Pros
Straightforward and easy to understand.
Correctly solves the problem for the given constraints.
Cons
Inefficient for large input strings due to its quadratic time complexity.
It re-checks many overlapping substrings, leading to redundant computations.
A more optimal solution uses the sliding window technique. This approach maintains a 'window' (a substring) that is always valid or is immediately corrected to become valid. The window expands by moving a right pointer and shrinks by moving a left pointer, ensuring the condition of at most two occurrences per character is met. This avoids re-computation by efficiently updating the window in a single pass over the string.
Algorithm
- Initialize a frequency map
counts(an array of size 26), aleftpointer to 0, andmaxLengthto 0. - Iterate through the string with a
rightpointer from0ton-1. - For each character
charRight = s.charAt(right), increment its count in thecountsmap. - Enter a
whileloop that checks if the count ofcharRighthas exceeded 2. - Inside the
whileloop, shrink the window from the left: decrement the count ofs.charAt(left)and increment theleftpointer. - The loop continues until the window is valid again (i.e., the count of
charRightis no more than 2). - After the window is guaranteed to be valid, calculate its current length
right - left + 1and updatemaxLength. - After the
forloop finishes, returnmaxLength.
Walkthrough
We use two pointers, left and right, to define the current window s.substring(left, right + 1). We also use a frequency map, counts, to store character frequencies within this window.
The right pointer iterates from the beginning to the end of the string to expand the window. At each step, we add s.charAt(right) to the window and increment its count.
If adding s.charAt(right) causes its count to become 3, the window becomes invalid. To fix this, we shrink the window from the left by moving the left pointer to the right. We decrement the count of the character at the left pointer and advance left. We repeat this shrinking process until the count of s.charAt(right) is back to 2, making the window valid again.
After each step of the right pointer (and any necessary shrinking), the current window s.substring(left, right + 1) is guaranteed to be valid. We then update our maxLength with the length of this current valid window. This single pass ensures linear time complexity.
class Solution { public int maximumLengthSubstring(String s) { int[] counts = new int[26]; int left = 0; int maxLength = 0; int n = s.length(); for (int right = 0; right < n; right++) { char charRight = s.charAt(right); counts[charRight - 'a']++; // If the count of the character just added exceeds 2, // we need to shrink the window from the left until its count is valid again. while (counts[charRight - 'a'] > 2) { char charLeft = s.charAt(left); counts[charLeft - 'a']--; left++; } // The window s[left..right] is now valid. // Update the maximum length found so far. maxLength = Math.max(maxLength, right - left + 1); } return maxLength; }}Complexity
Time
O(n), where n is the length of the string `s`. Each pointer, `left` and `right`, traverses the string at most once. This results in a single pass and linear time performance.
Space
O(1) or O(k), where k is the size of the character set (26). The frequency map has a fixed size, independent of the input string's length.
Trade-offs
Pros
Optimal time complexity of O(n).
Efficient in terms of space, using only a constant amount of extra space.
Scales well even for much larger strings.
Cons
The logic can be slightly more complex to reason about compared to a simple brute-force approach.
Solutions
Solution
class Solution {public int maximumLengthSubstring(String s) { int[] cnt = new int[26]; int ans = 0; for (int i = 0, j = 0; j < s.length(); ++j) { int idx = s.charAt(j) - 'a'; ++cnt[idx]; while (cnt[idx] > 2) { --cnt[s.charAt(i++) - 'a']; } ans = Math.max(ans, j - i + 1); } return ans; }}class Solution {public: int maximumLengthSubstring(string s) { int cnt[26]{}; int ans = 0; for (int i = 0, j = 0; j < s.length(); ++j) { int idx = s[j] - 'a'; ++cnt[idx]; while (cnt[idx] > 2) { --cnt[s[i++] - 'a']; } ans = max(ans, j - i + 1); } return ans; }};class Solution: def maximumLengthSubstring(self, s: str) -> int: cnt = Counter() ans = i = 0 for j, c in enumerate(s): cnt[c] += 1 while cnt[c] > 2: cnt[s[i]] -= 1 i += 1 ans = max(ans, j - i + 1) return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.