LeetCode [2696]: Minimum String Length After Removing Substrings

📌 LeetCode [2696]: Minimum String Length After Removing Substrings

🔗 문제 링크

---

문제 설명 📄

주어진 문자열 s에서, 다음 규칙에 따라 문자열을 변환합니다:

1. 문자열에서 "AB" 또는 "CD"가 연속된 경우 이를 제거합니다.
2. 제거한 뒤, 남은 문자열로 다시 같은 과정을 반복합니다.
3. 더 이상 "AB" 또는 "CD"를 제거할 수 없으면 문자열의 길이를 반환합니다.

목표: 최종적으로 남은 문자열의 길이를 계산하세요.

---

문제 접근 방식 📋

1. 스택을 활용:
   • 스택 자료구조를 이용해 "AB" 또는 "CD"를 제거합니다.
   • 스택의 마지막 문자와 현재 문자를 비교하여 규칙에 따라 제거 또는 추가 작업을 수행합니다.
2. 최종 결과:
   • 문자열 탐색이 끝난 후, 스택에 남은 문자의 개수가 최종 문자열의 길이가 됩니다.

---

Solution 💻

class Solution:
    def minLength(self, s: str) -> int:
        stack = []

        for i in s:
            if not stack:
                stack.append(i)
            elif stack[-1] == "A" and i == "B":
                stack.pop()
            elif stack[-1] == "C" and i == "D":
                stack.pop()
            else:
                stack.append(i)

        return len(stack)

시간 복잡도 ⏲️

• 문자열 순회: (O(n)), (n)은 문자열의 길이.
• 스택 연산: 각 문자는 한 번 추가되고 한 번 제거되므로 (O(n)).
• 총 시간 복잡도: (O(n)).

공간 복잡도 🗄️

• 스택 사용: 최악의 경우 (O(n)), 모든 문자가 스택에 추가되는 경우.
• 총 공간 복잡도: (O(n)).

---

리팩토링 🛠️

개선된 코드

class Solution:
    def minLength(self, s: str) -> int:
        stack = []
        pairs = {"A": "B", "C": "D"}  # 규칙을 딕셔너리로 정의

        for char in s:
            if stack and pairs.get(stack[-1]) == char:
                stack.pop()
            else:
                stack.append(char)

        return len(stack)

리팩토링 후 시간 복잡도 ⏲️

• 문자열 순회: (O(n)), (n)은 문자열의 길이.
• 스택 연산: (O(n)), 각 문자는 한 번 추가되고 한 번 제거됩니다.
• 총 시간 복잡도: (O(n)).

리팩토링 후 공간 복잡도 🗄️

• 스택 사용: 최악의 경우 (O(n)), 모든 문자가 스택에 추가되는 경우.
• 총 공간 복잡도: (O(n)).

---