3223. Minimum Length of String After Operations

https://leetcode.com/problems/minimum-length-of-string-after-operations/description/?envType=daily-question&envId=2025-01-13

 

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: 5Explanation: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. 각 문자의 등장횟수를 저장
2. 1 ~ length - 1까지 순회하면서 시작 Idx값을 정한다.
3. 등장횟수가 3 미만이라면 왼쪽, 오른쪽에 동일 문자가 존재할 수 없으므로 continue.
4. left를 탐색하며 동일 문자가 존재하는 경우 left idx값 갱신.
5. 마찬가지 right로 동일하게 해준다.
6. left, right idx가 -1이 아닌 경우에 StringBuilder에서 해당 인덱스 값을 제거하고, 등장횟수에서 2를 빼주며 인덱스 조정을 해준다.

참고로 나는 인덱스 조정을 생각하지 못해서 틀렸다.

i = Math.max(0, l - 1);

 

StringBuilder의 길이가 줄어듬에 따라서, 시작 인덱스의 위치도 조정이 필요했다.

하지만, 이렇게 했음에도 테스트 케이스 682/702 에서 걸렸다.

 

문제에서 s의 길이의 최댓값이 20만이고, 나의 코드에서 left, right를 검사하는 과정에서 worst case가 O(n^2)이기 때문에 시초가 발생했던 것이다.

 

다른 사람 풀이

class Solution {
    public int minimumLength(String s) {
        int [] occur = new int[26];

        for(char c : s.toCharArray()) {
            occur[c - 'a']++;
        }

        int len = 0;
        for(int val : occur) {
            if (val == 0) continue;
            if (val % 2 == 0) len += 2;
            else len += 1;
        }
        return len;
    }
}

 

정말 간단하게 풀었다.

나랑 동일하게 등장횟수를 저장했으나, 등장횟수를 저장한 배열을 순회하면서 길이 계산을 해주었다.

 

Input: s = "abaacbcbb" 

해당 예제에서 등장횟수는

a: 3,

b: 4,

c: 2

 

홀수인 경우엔 계속 문자열을 삭제하더라도 본인만 남으니 +1,

짝수인 경우엔 문자열이 2개가 남고 더이상 삭제를 할 수 없으니 +2를 해줬다.