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 <= 105
s
only consists of characters'a'
,'b'
, and'c'
.
Solution: Two Pointers + Greedy
Delete all the chars for each prefix and suffix pair.
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: int minimumLength(string s) { int l = 0, r = s.length() - 1; while (l < r) { if (s[l] != s[r]) break; const char c = s[l]; while (l <= r && s[l] == c) ++l; while (l <= r && s[r] == c) --r; } return r - l + 1; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment