LeetCode [1717]: Maximum Score From Removing Substrings

📌 LeetCode [1717]: Maximum Score From Removing Substrings

🔗 문제 링크

---

문제 설명 📄

문자열 s에서 다음 두 종류의 패턴을 제거할 수 있습니다:

• "ab" 제거 시 점수 x 추가
• "ba" 제거 시 점수 y 추가

문자열을 적절히 조작하여 얻을 수 있는 최대 점수를 반환하세요.

---

문제 해결 접근 🚀

1. "ab"와 "ba" 중 점수가 더 높은 것을 먼저 제거합니다.
2. 점수 크기 (x와 y)에 따라 처리 순서를 결정하여 불필요한 계산을 줄입니다.
3. 스택을 활용하여 문자열을 효율적으로 조작합니다.
4. 두 번의 제거 과정을 거쳐 최종 점수를 계산합니다.

---

Solution 💻

class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        def deleteS(s, target, plus):
            stack = []
            nonlocal point
            for i in s:
                if stack and stack[-1] == target[0] and i == target[1]:
                    stack.pop()
                    point += plus
                else:
                    stack.append(i)
            return stack

        point = 0
        if y < x:
            result = deleteS(s, "ab", x)
            deleteS("".join(result), "ba", y)
        else:
            result = deleteS(s, "ba", y)
            deleteS("".join(result), "ab", x)

        return point

---

시간 복잡도 분석 ⏲️

• 패턴 제거:
  • 각 패턴 제거는 문자열을 한 번 순회 (O(n))로 처리합니다.
  • 전체 시간 복잡도는 O(n).

공간 복잡도 분석 🗄️

• 스택 사용으로 추가 공간이 필요: O(n).
• 최종 공간 복잡도는 O(n).

---

리팩토링 🛠️

리팩토링 코드

class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        def delete_and_score(s, targets):
            stack = []
            score = 0
            for char in s:
                if stack and stack[-1] == targets[0] and char == targets[1]:
                    stack.pop()
                    score += targets[2]
                else:
                    stack.append(char)
            return "".join(stack), score

        if x > y:
            s, score1 = delete_and_score(s, ("a", "b", x))
            _, score2 = delete_and_score(s, ("b", "a", y))
        else:
            s, score1 = delete_and_score(s, ("b", "a", y))
            _, score2 = delete_and_score(s, ("a", "b", x))

        return score1 + score2

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

• 동일하게 O(n).

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

• 동일하게 O(n).