# 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

- 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.

- Start with a radius of zero, and see if
- Remove the matched characters and go back to before the removed segment.
- 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):
= 0
radius while (
- radius >= 0)
(index and (index + 1 + radius < n)
and s[index - radius] in HEADS
and HEADS[s[index - radius]] == s[index + radius + 1]
):+= 1
radius
return radius
def minLength(self, s: str) -> int:
= len(s)
n = 0
index while index < n:
if (radius := self.getRadius(s, n, index)) > 0:
= s[: index + 1 - radius] + s[index + radius + 1 :]
s -= 2 * radius
n -= radius - 1
index else:
+= 1
index
return n
```