Minimum Length of String After Operations(Hash Table,String,Counting)

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: 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.

 

Constraints:

• 1 <= s.length <= 2 * 105
• s consists only of lowercase English letters.

간만에 코륑 문제다.

뇌(?)를 풀겸 가볍게 풀어봅시다.

 

언제나 단골손님인 String에 관한 문제..!

 

 

1. Python

넘 쉬워서 당황;;

class Solution:
    def minimumLength(self, s: str) -> int:
        ans = 0
        from collections import Counter
        cnt = Counter(s)
        for ch, num in cnt.items():
            if num >=3 and num % 2 == 0:
                ans += 2
            elif num >=3 and num % 2 == 1:
                ans += 1
            else : ans += num
        return ans

 

2. C

int minimumLength(char* s) {
    int ans = 0;
    int* cnt = (int*)malloc(26*sizeof(int));
    //initialize cnt with value '0'
    memset(cnt,0,26*sizeof(int));

    int n = strlen(s);
    for(int i = 0; i<n; i++){
        cnt[s[i]-'a']++;
    }

    // calculate answer
    for(int i = 0; i<26; i++){
        if(cnt[i]==0) continue;
        else if(cnt[i]<=2) ans += cnt[i];
        else if(cnt[i]>2 && cnt[i]%2==0) ans += 2;
        else ans += 1;
    }
    free(cnt);
    return ans;
}

 

cnt를 0으로 초기화 할당할 땐, memset 안 쓰고 calloc을 쓰면 자동으로 0으로 할당되기도 한다.

int minimumLength(char* s) {
  int* counts = (int*) calloc(sizeof(int), 26);
  for (; *s; ++s) {
    ++counts[*s - 'a'];
  }

  int res = 0;
  for (int i = 0; i < 26; ++i) {
    if (counts[i]) {
      res += 2 - (counts[i] & 1);
    }
  }

  free(counts);
  return res;
}

 

 

3. C++

map에선 find쓰기가 편하다. 그냥 map.find(key) 하면 된다.

vector의 경우가 find(vec.begin() , vec.end(), value) != vec.end() 이런 식으로 해야 한다.

class Solution {
public:
    int minimumLength(string s) {
        int ans = 0;
        unordered_map<char,int> m;
        for(const char ch : s){
            if(m.find(ch)==m.end()) m[ch] = 1;
            else m[ch]++;
        }
        for(const auto pair : m){
            if(pair.second > 2 && pair.second % 2 == 0) ans +=2;
            else if(pair.second > 2 && pair.second % 2 == 1) ans +=1;
            else ans+=pair.second;
        }
        return ans;
    }
};