find-maximum-removals-from-source-string.py

# Time:  O(n * m)
# Space: O(n + m)

# dp
class Solution(object):
    def maxRemovals(self, source, pattern, targetIndices):
        """
        :type source: str
        :type pattern: str
        :type targetIndices: List[int]
        :rtype: int
        """
        dp = [float("-inf")]*(len(pattern)+1)
        dp[0] = 0
        lookup = [False]*len(source)
        for x in targetIndices:
            lookup[x] = True
        for i in xrange(len(source)):
            for j in reversed(xrange(len(pattern)+1)):
                dp[j] += lookup[i]
                if j-1 >= 0 and pattern[j-1] == source[i]:
                    dp[j] = max(dp[j], dp[j-1])
        return dp[-1]