[LeetCode] 3223. Minimum Length of String After Operations (Python)

 

 

난이도: Medium

 

문제 설명

---

You are given a string s.

You can perform the following process on s any number of times:

• Choose an index i in the string such that there is at least one character to the left of index i that is equal to s[i], and at least one character to the right that is also equal to s[i].
• Delete the closest character to the left of index i that is equal to s[i].
• Delete the closest character to the right of index i that is equal to s[i].

Return the minimum length of the final string s that you can achieve.

 

문제 예제

---

Example 1:

Input: s = "abaacbcbb"

Output: 5

Explanation:
We do the following operations:

• Choose index 2, then remove the characters at indices 0 and 3. The resulting string is s = "bacbcbb".
• Choose index 3, then remove the characters at indices 0 and 5. The resulting string is s = "acbcb".

Example 2:

Input: s = "aa"

Output: 2

Explanation:
We cannot perform any operations, so we return the length of the original string.

 

제한 사항

---

• 1 <= s.length <= 2 * 10^5
• s consists only of lowercase English letters.

 

 

✏️Solution(솔루션)

---

class Solution:
    def minimumLength(self, s: str) -> int:
        count_s = Counter(s)
        answer = len(s)

        for alpha in count_s:
            while count_s[alpha] > 2:
                count_s[alpha] -= 2
                answer -=2
        
        return answer

 

먼저, s에 있는 알파벳들의 갯수를 Counter를 통해 저장했다.

 

문제를 보고 3개 이상의 갯수를 가지는 알파벳들만 뺄 수 있을 거 같았기 때문이다.

 

저장한 count_s에서 count_s[alpha]가 3이상이라면 3보다 작아질 때까지 -2를 해주었다.

answer 역시 처음 s길이를 저장해놓고 -2를 해주었다.

 

마지막으로 이 answer를 return하여 정답을 맞출 수 있었다.

 

풀고 나니 굳이 while문으로 계산할 필요가 없을 것 같았다. 괜히 시간만 더들고...

따라서, 다음과 같이 코드를 수정했고 이 역시 정답을 맞출 수 있었다.

class Solution:
    def minimumLength(self, s: str) -> int:
        count_s = Counter(s)
        answer = len(s)

        for alpha in count_s:
            if count_s[alpha] > 2:
                if count_s[alpha] % 2 == 1:
                    answer -= (count_s[alpha]) - 1
                else:
                    answer -= (count_s[alpha]) - 2

        return answer

---

문제: 3223. Minimum Length of String After Operations

 

깃허브: github

algorithmPractice/LeetCode/3455-minimum-length-of-string-after-operations at main · laewonJeong/algorithmPractice