솔루션: 부분 문자열 제거의 최대 점수(버전 2)

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 드셨거나 유용하셨다면 이 게시물에 좋아요를 누르거나 추천my solution post on Leetcode's forums 해주세요.


참고: 이것은 이 문제에 대한 솔루션 게시물의 두 번째 버전입니다. 이것이 더 나은 솔루션이지만 .

Leetcode 문제 #1717(중간): 부분 문자열 제거의 최대 점수

설명:

문자열s과 두 개의 정수x 및 y가 제공됩니다. 두 가지 유형의 작업을 여러 번 수행할 수 있습니다.

부분 문자열"ab"을 제거하고 x점을 얻습니다.

예를 들어 "ab"에서 "cabxbae"를 제거하면 "cxbae" 가 됩니다.

부분 문자열"ba"을 제거하고 점수y를 얻습니다.

예를 들어 "ba"에서 "cabxbae"를 제거하면 "cabxe" 가 됩니다.

s 에 위의 연산을 적용한 후 얻을 수 있는 최대 점수를 반환합니다.


예:


예 1:



입력:
s = "cdbcbbbaaabab", x = 4, y = 5

산출:
19

설명:
"cdbcbbbaaaab"에서 밑줄이 그어진 "ba"를 제거합니다. 이제 s = "cdbcbbbaaab"이고 5점이 점수에 추가됩니다. "cdbcbbaaab"에서 밑줄이 그어진 "ab"를 제거합니다. 이제 s = "cdbcbbaa"이고 4점이 추가됩니다. "cdbcbbaa"에 밑줄이 그어진 "ba"를 제거합니다. 이제 s = "cdbcba"이고 5점이 점수에 추가됩니다. "cdbcba"에 밑줄이 그어진 "ba"를 제거합니다.지금, s = "cdbc"및 5점이 점수에 추가됩니다. 총점 = 5 + 4 + 5 + 5 = 19입니다.



예 2:



입력:
s = "aabbaaxybbbaabb", x = 5, y = 4

산출:
20



제약:

1 <= s.length <= 10^5

1 <= x, y <= 10^4

s는 영문 소문자로 구성되어 있습니다.

아이디어:

참고: 이것은 이 문제에 대한 두 번째 솔루션 게시물입니다. 나는 여전히 the other solution이 멋진 접근 방식이라고 생각하지만 이 방식이 확실히 더 효율적이고 따르기 쉽습니다.

이 문제에 대해 쉽게 깨달을 수 있는 것 중 하나는 문자열을 덩어리로 나눌 수 있다는 것입니다. "a"와 "b"의 연속 세트만 의미가 있으며, 이 두 문자가 아닌 다른 문자를 볼 때마다 한 세그먼트를 효과적으로 종료하고 다른 세그먼트가 시작되기를 기다립니다.

우리가 상당히 쉽게 깨달을 수 있는 또 다른 것은 우리가 어떤 패턴이 더 가치가 있는지 탐욕스럽게 우선순위를 정해야 한다는 것입니다. 일을 더 쉽게 하기 위해 어떤 패턴이 더 높은 값을 갖는지에 따라 일부 변수 스왑을 메인 코드에 접두사로 붙일 수 있습니다. 이 게시물의 나머지 부분에서는 "ab"> "ba", 따라서 = "a"및 b = "b"라고 가정할 수 있습니다.

""와 "b"가 혼합된 세그먼트를 고려하면 해당 세그먼트를 통과하고 더 나은 패턴에 대한 모든 일치 항목을 설명하는 데 문제가 거의 없습니다. 나중의 b와 일치시키기 위해 현재 진행 상황보다 바로 뒤에 있는 a가 몇 개인지 계속 추적해야 합니다.

그러나 가능한 한 X 패턴을 일치시킨 후 Y 패턴을 일치시키는 것은 어떻게 처리합니까? 이에 대한 답을 얻으려면 수정된 문자열이 어떻게 생겼는지 생각해야 합니다.

segment = "bbaababbaa"                       // initial segment
segment = "bbaa"                             // after pulling out all "ab" patterns

segment = "bbbbabababaaabababaaaabababaaa"   // initial segment
segment = "bbbbaaaaaaaa"                     // after pulling out all "ab" patterns

가능한 모든 "ab"패턴을 일치시킨 후 유사한 모양의 나머지 세그먼트가 항상 남게 된다는 것을 알 수 있습니다. 다수의 b 다음에 다수의 a가 옵니다. 여기에서 a와 b 사이에 가장 작은 수만큼 "ba"일치를 만들 수 있습니다.

그런 다음 각 세그먼트의 끝에 도달하면 저장소를 지우는 것을 기억해야 합니다.


구현:

다른 언어와 달리 Java에는 변수 내용을 교환하는 편리한 방법이 없습니다.

S의 끝을 지나서 반복을 실행하거나, 마지막 세그먼트가 S의 끝까지 올라갈 경우를 대비하여 최종 Y 일치를 반환 값에 추가해야 합니다.


자바스크립트 코드:

var maximumGain = function(S, X, Y) {
    let len = S.length, ans = 0, a = "a", b = "b"
    if (Y > X) [a,b,X,Y] = [b,a,Y,X]
    let aStore = 0, bStore = 0
    for (let i = 0, c = S[i]; i <= len; c = S[++i])
        if (c === a) aStore++
        else if (c === b)
            if (aStore) ans += X, aStore--
            else bStore++
        else ans += Y * Math.min(aStore, bStore), aStore = bStore = 0
    return ans
};

파이썬 코드:

class Solution:
    def maximumGain(self, S: str, X: int, Y: int) -> int:
        a,b, ans, aStore,bStore = "a","b", 0, 0,0
        if Y > X: a,b,X,Y = b,a,Y,X
        for c in S:
            if c == a: aStore += 1
            elif c == b:
                if aStore:
                    ans += X
                    aStore -= 1
                else: bStore += 1
            else:
                ans += Y * min(aStore, bStore)
                aStore,bStore = 0,0
        return ans + Y * min(aStore, bStore)

자바 코드:

class Solution {
    public int maximumGain(String S, int X, int Y) {
        char a = 'a', b = 'b';
        int ans = 0, aStore = 0, bStore = 0;
        if (Y > X) {
            char ctemp = a;
            a = b;
            b = ctemp;
            int itemp = X;
            X = Y;
            Y = itemp;
        }
        for (char c: S.toCharArray())
            if (c == a) aStore++;
            else if (c == b)
                if (aStore > 0) {
                    ans += X;
                    aStore--;
                } else bStore++;
            else {
                ans += Y * Math.min(aStore, bStore);
                aStore = bStore = 0;
            }
        return ans + Y * Math.min(aStore, bStore);
    }
}

C++ 코드:

class Solution {
public:
    int maximumGain(string S, int X, int Y) {
        char a = 'a', b = 'b';
        int ans = 0, aStore = 0, bStore = 0;
        if (Y > X) swap(a,b), swap(X,Y);
        for (char c: S)
            if (c == a) aStore++;
            else if (c == b)
                if (aStore > 0) ans += X, aStore--;
                else bStore++;
            else ans += Y * min(aStore, bStore), aStore = bStore = 0;
        return ans + Y * min(aStore, bStore);
    }
};