[LeetCode/Easy] 2716. Minimize String Length

1. Input

1) String s

 

2. Output

1) s에서 다음과 같은 작업을 수행했을 때 만들 수 있는 문자열의 길이 중 가장 작은 것을 반환

- 0부터 s.length()-1 사이의 인덱스 i를 고른다.

- i번째 문자를 c라고 할 때, i를 기준으로 가장 가까운 c를 왼쪽에서 1개 오른쪽에서 1개를 지운다.

- 더 이상 지울 수 없을 때까지 반복한다.

 

3. Constraint

1) 1 <= s.length <= 100

2) s는 영어 소문자로 이루어져 있다.

 

4. Example

Input: s = "aaabc" -> Output: 3

설명:

- i=1, c='a': i의 왼쪽과 오른쪽에서 가장 가까운 a인 0번째와 2번째를 지운다. -> “abc"

- 더 이상 지울 수 있는 것이 없으므로 3을 반환한다.

 

5. Code

1) 첫 코드

class Solution {
    public int minimizedStringLength(String s) {
        Set<Character> set = new HashSet<>();
        for(int i=0 ; i<s.length() ; i++)
            set.add(s.charAt(i));
        return set.size();
    }
}

- 80%, 39%

 

2) 비교해보고 싶어서 다시 풀어본 코드

class Solution {
    public int minimizedStringLength(String s) {
        boolean[] abc = new boolean[26];
        int count = 0;
        for(int i=0 ; i<s.length() ; i++){
            if(!abc[s.charAt(i)-'a']) {
                abc[s.charAt(i)-'a'] = true;
                count++;
            }
        }
        return count;
    }
}

- 100%, 98%

- 워 역시.. hash를 쓰는 게 비용이 좀 더 들긴 하나보다.