[LeetCode] 1750. Minimum Length of String After Deleting Similar Ends

https://leetcode.com/problems/minimum-length-of-string-after-deleting-similar-ends/description/

Minimum Length of String After Deleting Similar Ends - LeetCode

Leetcode - Minimum Length of String After Deleting Similar Ends

문제 유형 : 문자열 처리, 투 포인터

문제 난이도 : Medium

 

문제

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:

1. Pick a non-empty prefix from the string s where all the characters in the prefix are equal.
2. Pick a non-empty suffix from the string s where all the characters in this suffix are equal.
3. The prefix and the suffix should not intersect at any index.
4. The characters from the prefix and suffix must be the same.
5. 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).

 

문자열 s의 문자는 a, b, c만 있습니다. 아래의 알고리즘을 몇 번이고 사용할 수 있습니다:

1. 문자가 모두 같은 접두사를 고를 수 있습니다.
2. 문자가 모두 같은 접미사를 고를 수 있습니다.
3. 접두사와 접미사는 교차할 수 없습니다.
4. 접두사와 접미사의 문자는 같아야합니다.
5. 양쪽 접두사와 접미사를 지웁니다.

문자열 s가 알고리즘을 사용하여 얻을 수 있는 최소 길이를 구하시오.

 

풀이

투 포인터를 이용해서 left = 0과 right = n-1인덱스부터 시작한다. left < right인동안 실행한다.

우선, s[left]와 s[right]이 서로 다르면 반복문을 바로 종료한다.

그게 아니라면, left와 right이 서로 교차하지 않는 선에서 접두사와 접미사를 각각 확장시킨다.

 

이렇게 left와 right의 사이를 최대한 좁히고, right - left + 1을 반환하면 최소 문자열의 길이가 나온다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int minimumLength(string s) {
        const int n = s.size();
        int left = 0;
        int right = n-1;

        while(left < right) {
            if(s[left] != s[right]) break;
            auto ch = s[left];
            while(left+1 < right && s[left+1] == ch) {
                left++;
            }

            while(left < right-1 && s[right-1] == ch) {
                right--;
            }

            left++;
            right--;
        }

        return right-left+1;
    }
};