Daily Challenge 10/07/2024: Minimum String Length After Removing Substrings

Remove nested substrings from a string.

See the full problem statement on leetcode.

Analysis

Examples

Iteration 1:
ABFCACDB
^^
index=0

Iteration 2:
FCACDB
^
index=0

Iteration 3:
FCACDB
 ^
 index=1

Iteration 4:
FCACDB
 ^^^^
  index=2

Iteration 5:

FB
 ^ index=2

CACACABDBDBDB
     ^^ radius = 1
CACACABDBDBDB
    ^  ^ radius = 2
CACACABDBDBDB
   ^    ^ radius = 3
CACACABDBDBDB
  ^      ^ radius = 4
CACACABDBDBDB
 ^        ^ radius = 5
CACACABDBDBDB
^          ^ radius = 6

CCDAABBDCD
 ^^
 index=1, retreat by radius minus 1 (0).

CAABBDCD
 ^
 index=1

CAABBDCD
^^^^^^ 
  index=2, retreat by 2.

CD
^^ index=0, retreat by 1

Algorithm

1. Look at the current character.
   • Start with a radius of zero, and see if s[index + radius] is A or C. If it is not, the return zero - otherwise check that s[index + radius + 1] is the corresponding end. Increment the radius by one and see if this still holds, and keep going until the radius brings the indices out of bounds or characters do not match.
2. Remove the matched characters and go back to before the removed segment.
3. Return the length of the remaining string.

Solution

My initial solution always retreated to the very start, which caused some terrible performance (only beat \(7\%\) in both runtime and memory). I fixed it to retreat only to the character before those matched and beat \(78\%\) in runtime.

class Solution:
    def getRadius(self, s: str, n: int, index: int):

        radius = 0
        while (
            (index - radius >= 0)
            and (index + 1 + radius < n)
            and s[index - radius] in HEADS
            and HEADS[s[index - radius]] == s[index + radius + 1]
        ):
            radius += 1

        return radius

    def minLength(self, s: str) -> int:

        n = len(s)
        index = 0
        while index < n:
            if (radius := self.getRadius(s, n, index)) > 0:
                s = s[: index + 1 - radius] + s[index + radius + 1 :]
                n -= 2 * radius
                index -= radius - 1
            else:
                index += 1

        return n