Minimum String Length After Removing Substrings[E,StringStackSimulation]

https://leetcode.com/problems/minimum-string-length-after-removing-substrings/description/?envType=daily-question&envId=2024-10-07

You are given a string s consisting only of uppercase English letters.

You can apply some operations to this string where, in one operation, you can remove any occurrence of one of the substrings "AB" or "CD" from s.

Return the minimum possible length of the resulting string that you can obtain.

Note that the string concatenates after removing the substring and could produce new "AB" or "CD" substrings.

 

Example 1:

Input: s = "ABFCACDB"
Output: 2
Explanation: We can do the following operations:
- Remove the substring "ABFCACDB", so s = "FCACDB".
- Remove the substring "FCACDB", so s = "FCAB".
- Remove the substring "FCAB", so s = "FC".
So the resulting length of the string is 2.
It can be shown that it is the minimum length that we can obtain.

Example 2:

Input: s = "ACBBD"
Output: 5
Explanation: We cannot do any operations on the string so the length remains the same.

 

Constraints:

• 1 <= s.length <= 100
• s consists only of uppercase English letters.

1. Python

파이썬에는 역시 각종 method 들이 많아서 짧게 풀 수 있었다.

class Solution:
    def minLength(self, s: str) -> int:
        while "AB" in s or "CD" in s :
            s = s.replace("AB","")
            s = s.replace("CD","")
        return len(s)

 

근데 답지를 보니까 Stack을 많이 썼네. C++로는 Stack을 써보자

 

2. C++

class Solution {
public:
    int minLength(string s) {
        stack<char> arr;
        for(char c : s){
            //AB filtering
            if(!arr.empty() && c == 'B'){
                if(arr.top()=='A'){
                    arr.pop();
                    continue;
                }
            }
            //CD filtering
            if(!arr.empty() && c == 'D'){
                if(arr.top() == 'C'){
                    arr.pop();
                    continue;
                }
            }
            //No filtering case
            arr.push(c);
        }
        return arr.size();
    }
};

 

3. C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int minLength(char *s) {
    int n = strlen(s);
    char* ans = (char*)malloc((n + 1) * sizeof(char));  // 동적 메모리 할당, n+1은 null 문자 추가를 위해
    int idx = 0;

    for (int i = 0; i < n; i++) {
        // 패턴 'AB'를 제거
        if (s[i] == 'B' && idx > 0 && ans[idx - 1] == 'A') {
            idx--;  // 이전 'A'를 제거
            continue;
        }
        // 패턴 'CD'를 제거
        if (s[i] == 'D' && idx > 0 && ans[idx - 1] == 'C') {
            idx--;  // 이전 'C'를 제거
            continue;
        }
        ans[idx++] = s[i];  // 현재 문자를 결과 배열에 추가
    }

    ans[idx] = '\0';  // 문자열의 끝에 null 문자 추가
    int resultLength = strlen(ans);  // 결과 문자열의 길이 계산

    free(ans);  // 동적 메모리 해제
    return resultLength;
}