_1717. Maximum Score From Removing Substrings.md

1717. Maximum Score From Removing Substrings

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 12, 2024

Last updated : July 12, 2024

---

Related Topics : String, Stack, Greedy

Acceptance Rate : 62.8 %

---

Logic:

• We should always take the greater value option if it's avalible.
• Cases where both are (e.g. aba or bab) we should still take the greater option.
• We should parse just the greater value option first in case finding it and removing it causes another to appear. E.g. with aaabbb if ab is worth more than ba we remove ab, then ab again, etc.
• Reverse the stack each iteration / reverse the ordering we use since transfering the values of one stack to another reverses the order they will be popped in.

Version 1

Lot of redundancy here but it works. I tried chunking the input string into groups of just 
`abababaaababa` style strings, breaking them when there were non(a,b) characters 
since I thought I would need multiple passes so this was to remove that redundancy 
of checking non(a,b) strings. This was later realized to be unnecessary when 
I was optimizing my code

Version 2

Removed the redundancy of setting the new `findX` and `findY` values.
- We only have to check the larger one first then the smaller one
- Only 2 passes (one for each) are neccessary.
- The pass for the larger one is guarenteed to remove all instances leaving
  a string of (...aaaabbbbb...) or (...bbbbaaaa...)

Previously, my code was checking for both and resetting the search if 
one was found, which was redundant since it was making extra passes 
when not neccessary.

Version 3

I split my code away from chunking since that became unnecessary 
since I was only doing 2 passes and finding the chunks would be 
a pass on its own making the benefit nonexistant. This removed a 
number of lines too and removed the need for extra variables such 
as the check for reversing the stack for instance.

---

Solutions

• m1717 Daily v2.py
• m1717 Daily v3.py
• m1717 Daily.py

Python

m1717 Daily v2.py

class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        # Non-(a,b) chars act as boundaries and don't affect the final score
        chunks = re.findall('[a-b]+', s)

        # Store largest in x
        t1, t2 = 'ab', 'ba'
        if y > x :
            x, y = y, x
            t1, t2 = t2, t1

        # Parse each chunk
        output = 0
        for chk in chunks :
            rev = False
            findX = True
            findY = True
            stk = list(chk)

            # findX: check for the larger value ab/ba
            # findY: check for the smaller
            while findX or findY :
                stk2 = []
                target = t1 if findX else t2
                targetRew = x if findX else y

                while stk :
                    if not stk2 :
                        stk2.append(stk.pop())
                        continue

                    curr = stk[-1] + stk2[-1] if not rev else stk2[-1] + stk[-1]
                    if curr == target :
                        output += targetRew
                        stk.pop()
                        stk2.pop()
                        continue
                    stk2.append(stk.pop())

                if not findX :
                    break
                findX = False

                # reverse ab ba since stack appending to another stack
                # reverses the order
                rev = not rev
                stk = stk2

        return output

m1717 Daily v3.py

class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        # Store largest in x
        t1, t2 = 'ab', 'ba'
        if y > x :
            x, y = y, x
            t1, t2 = t2, t1

        output = 0
        stk = list(s)

        # Parse greater value substring
        stk2 = []
        while stk :
            if not stk2 :
                stk2.append(stk.pop())
                continue

            curr = stk[-1] + stk2[-1]
            if curr == t1 :
                output += x
                stk.pop()
                stk2.pop()
                continue
            stk2.append(stk.pop())
        stk = stk2

        # Parse lower value substring
        stk2 = []
        while stk :
            if not stk2 :
                stk2.append(stk.pop())
                continue

            curr = stk2[-1] + stk[-1]
            if curr == t2 :
                output += y
                stk.pop()
                stk2.pop()
                continue
            stk2.append(stk.pop())

        return output

m1717 Daily.py

class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        # Non-(a,b) chars act as boundaries and don't affect the final score
        chunks = re.findall('[a-b]+', s)

        # Store largest in x
        t1, t2 = 'ab', 'ba'
        if y > x :
            x, y = y, x
            t1, t2 = t2, t1

        # Parse each chunk
        output = 0
        for chk in chunks :
            rev = False
            findX = True
            findY = True
            stk = list(chk)

            # findX: check for the larger value ab/ba
            # findY: check for the smaller
            while findX or findY :
                stk2 = []
                target = t1 if findX else t2
                targetRew = x if findX else y
                found = False
                while stk :
                    if not stk2 :
                        stk2.append(stk.pop())
                        continue

                    curr = stk[-1] + stk2[-1] if not rev else stk2[-1] + stk[-1]
                    if curr == target :
                        output += targetRew
                        found = True
                        stk.pop()
                        stk2.pop()
                        continue
                    stk2.append(stk.pop())

                if not found :
                    if findX :          # larger not found, try smaller
                        findX = False
                    else :              # smaller not found, break
                        findY = False
                else :                  # found! retry both
                    findX = True
                    findY = True

                # reverse ab ba since stack appending to another stack
                # reverses the order
                rev = not rev
                stk = stk2

        return output