3090. Maximum Length Substring With Two Occurrences
Description
Given a string 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 <= 100
s
consists only of lowercase English letters.
Solutions
Solution 1: Two Pointers
We use two pointers $i$ and $j$ to maintain a sliding window, and an array $cnt$ to record the occurrence times of each character in the window.
In each iteration, we add the character $c$ at the pointer $j$ into the window, then check if $cnt[c]$ is greater than $2$. If it is, we move the pointer $i$ to the right until $cnt[c]$ is less than or equal to $2$. At this point, we update the answer $ans = \max(ans, j - i + 1)$.
Finally, we return the answer $ans$.
The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(|\Sigma|)$, where $\Sigma$ is the character set, and in this problem, $\Sigma = 26$.
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|