Description#
Given a string s consisting only of characters 'a', 'b', and 'c'. You are asked to apply the following algorithm on the string any number of times:
- Pick a non-empty prefix from the string
s where all the characters in the prefix are equal. - Pick a non-empty suffix from the string
s where all the characters in this suffix are equal. - The prefix and the suffix should not intersect at any index.
- The characters from the prefix and suffix must be the same.
- Delete both the prefix and the suffix.
Return the minimum length of s after performing the above operation any number of times (possibly zero times).
Example 1:
Input: s = "ca"
Output: 2
Explanation: You can't remove any characters, so the string stays as is.
Example 2:
Input: s = "cabaabac"
Output: 0
Explanation: An optimal sequence of operations is:
- Take prefix = "c" and suffix = "c" and remove them, s = "abaaba".
- Take prefix = "a" and suffix = "a" and remove them, s = "baab".
- Take prefix = "b" and suffix = "b" and remove them, s = "aa".
- Take prefix = "a" and suffix = "a" and remove them, s = "".
Example 3:
Input: s = "aabccabba"
Output: 3
Explanation: An optimal sequence of operations is:
- Take prefix = "aa" and suffix = "a" and remove them, s = "bccabb".
- Take prefix = "b" and suffix = "bb" and remove them, s = "cca".
Constraints:
1 <= s.length <= 105s only consists of characters 'a', 'b', and 'c'.
Solutions#
Solution 1: Two pointers#
We define two pointers $i$ and $j$ to point to the head and tail of the string $s$ respectively, then move them to the middle until the characters pointed to by $i$ and $j$ are not equal, then $\max(0, j - i + 1)$ is the answer.
The time complexity is $O(n)$ and the space complexity is $O(1)$. Where $n$ is the length of the string $s$.
1
2
3
4
5
6
7
8
9
10
| class Solution:
def minimumLength(self, s: str) -> int:
i, j = 0, len(s) - 1
while i < j and s[i] == s[j]:
while i + 1 < j and s[i] == s[i + 1]:
i += 1
while i < j - 1 and s[j - 1] == s[j]:
j -= 1
i, j = i + 1, j - 1
return max(0, j - i + 1)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int minimumLength(String s) {
int i = 0, j = s.length() - 1;
while (i < j && s.charAt(i) == s.charAt(j)) {
while (i + 1 < j && s.charAt(i) == s.charAt(i + 1)) {
++i;
}
while (i < j - 1 && s.charAt(j) == s.charAt(j - 1)) {
--j;
}
++i;
--j;
}
return Math.max(0, j - i + 1);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int minimumLength(string s) {
int i = 0, j = s.size() - 1;
while (i < j && s[i] == s[j]) {
while (i + 1 < j && s[i] == s[i + 1]) {
++i;
}
while (i < j - 1 && s[j] == s[j - 1]) {
--j;
}
++i;
--j;
}
return max(0, j - i + 1);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| func minimumLength(s string) int {
i, j := 0, len(s)-1
for i < j && s[i] == s[j] {
for i+1 < j && s[i] == s[i+1] {
i++
}
for i < j-1 && s[j] == s[j-1] {
j--
}
i, j = i+1, j-1
}
return max(0, j-i+1)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| function minimumLength(s: string): number {
let i = 0;
let j = s.length - 1;
while (i < j && s[i] === s[j]) {
while (i + 1 < j && s[i + 1] === s[i]) {
++i;
}
while (i < j - 1 && s[j - 1] === s[j]) {
--j;
}
++i;
--j;
}
return Math.max(0, j - i + 1);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| impl Solution {
pub fn minimum_length(s: String) -> i32 {
let s = s.as_bytes();
let n = s.len();
let mut start = 0;
let mut end = n - 1;
while start < end && s[start] == s[end] {
while start + 1 < end && s[start] == s[start + 1] {
start += 1;
}
while start < end - 1 && s[end] == s[end - 1] {
end -= 1;
}
start += 1;
end -= 1;
}
(0).max(end - start + 1) as i32
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| int minimumLength(char* s) {
int n = strlen(s);
int start = 0;
int end = n - 1;
while (start < end && s[start] == s[end]) {
while (start + 1 < end && s[start] == s[start + 1]) {
start++;
}
while (start < end - 1 && s[end] == s[end - 1]) {
end--;
}
start++;
end--;
}
if (start > end) {
return 0;
}
return end - start + 1;
}
|
