Maximum cost obtained by removing substring

Question

I have a string S containing only two characters "x" and "y". I also have an array A of positive integers of same length as of S. I can remove a sub-string of any positive length(>0) if that sub-string is having all same characters. The score of this move is A[len] where len is the length of sub-string removed and indexing is 1-based (because we can not remove 0 length sub-string). I can further remove such sub-strings until it gets empty and score will keep adding on. I want to maximise this score. It is not necessary to minimise the number of moves.

For example, let S = "xyy" and A = [2,3,1];I can choose substring S[1:2]="yy", resultant string will be "x" and score is 3;Now I can choose S[0:0]="x", resultant string is "" and score is 5;

One other way is,choose S[0:0], resultant string is "yy", score is 2;choose S[0:0], resultant string is "y", score is 4;choose S[0:0], resultant string is "", score is 6 which is higher than before.

I couldn't think of a greedy solution so tried brute-force:

# Checks if the chosen substring has all same characters or not
def check(s):return True if len(set(s)) == 1 else False

def cost(s):
    n = len(s)
    if n == 0:return 0
    if n == 1:return a[0]
    mx = -1

    # Try to remove all the substrings that satisfy the condition
    # And further check for resultant string after removal
    for i in range(n):
        for j in range(i,n):
            sub = s[i:j+1]
            if check(sub):mx = max(mx, a[len(sub)-1] + cost(s[:i]+s[j+1:]))
    return mx

This solution works for strings having length upto 8 but stucks otherwise (Based on my system config) so I added memoization into it :

# Checks if the chosen substring has all same characters or not
def check(s):return True if len(set(s)) == 1 else False

dp = dict()

def cost(s):
    # If this string is present in dp, return score
    if s in dp:return dp[s]
    n = len(s)
    if n == 0:return 0
    if n == 1:return a[0]
    mx = -1

    # Try to remove all the substrings that satisfy the condition
    # And further check for resultant string after removal

    for i in range(n):
        for j in range(i,n):
            sub = s[i:j+1]
            if check(sub):mx = max(mx, a[len(sub)-1] + cost(s[:i]+s[j+1:]))

    dp[s] = mx
    return mx

And it works for string having length upto 20. It fulfils my current requirement but can it be further optimised? It is simply a brute force solution so it doesn't look very satisfactory for string having length more than 20.

Can it be optimized to polynomial time O(N^2) or O(N^3)?

user_7326738 · Answer

A possible approach is to use itertools.groupby to compute the subgroups beforehand, and then use recursion with a generator to get the combinations. This way, you only have to iterate over each subgroup once:

from itertools import groupby
s = "xyy" 
a = [2,3,1]
def max_score(d, a, c = []):
   if d:
      for i in range(len(d[0])):
         yield from max_score(([] if not (k:=d[0][i+1:]) else [k])+d[1:], a, c+[a[i]])
   else:
      yield sum(c)

print(max(max_score([list(b) for _, b in groupby(s)], a)))

Output:

Timings:

import random, time
def get_test_data(size):
   s = ''.join(random.choice(['x', 'y']) for _ in range(size))
   return [list(b) for _, b in groupby(s)], [random.randint(1, 10) for _ in s]

def av_time(s):
   t = time.time()
   _ = max(max_score(*get_test_data(s)))
   return time.time() - t

for i in [10, 20, 30, 40]:
    print(f'---------Size:{i}, Average time:{sum(av_time(i) for _ in range(10))/float(10)}---------')

Output:

---------Size:10, Average time:0.00027167797088623047---------
---------Size:20, Average time:0.010815811157226563---------
---------Size:30, Average time:0.3306509256362915---------
---------Size:40, Average time:13.801056122779846---------

This solution can quickly compute results on strings with len(s) <= 30, but has slower times for larger sizes.

Maximum cost obtained by removing substring

1 Answers