Skip to content

3316. Find Maximum Removals From Source String 👍

Approach 1: Top-down

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  int maxRemovals(string source, string pattern, vector<int>& targetIndices) {
    const unordered_set<int> target{targetIndices.begin(), targetIndices.end()};
    vector<vector<int>> mem(source.length(), vector<int>(pattern.length(), -1));
    const int ans = maxRemovals(source, pattern, 0, 0, target, mem);
    return ans == INT_MIN ? 0 : ans;
  }

 private:
  // Returns the maximum number of operations that can be performed for
  // source[i..m) and pattern[j..n).
  int maxRemovals(const string& source, const string& pattern, int i, int j,
                  const unordered_set<int>& target, vector<vector<int>>& mem) {
    if (i == source.length())
      return j == pattern.length() ? 0 : INT_MIN;
    if (j == pattern.length())
      return (target.contains(i) ? 1 : 0) +
             maxRemovals(source, pattern, i + 1, j, target, mem);
    if (mem[i][j] != -1)
      return mem[i][j];
    const int pick =
        source[i] == pattern[j]
            ? maxRemovals(source, pattern, i + 1, j + 1, target, mem)
            : INT_MIN;
    const int skip = (target.contains(i) ? 1 : 0) +
                     maxRemovals(source, pattern, i + 1, j, target, mem);
    return mem[i][j] = max(pick, skip);
  };
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public int maxRemovals(String source, String pattern, int[] targetIndices) {
    Set<Integer> target = Arrays.stream(targetIndices).boxed().collect(Collectors.toSet());
    Integer[][] mem = new Integer[source.length()][pattern.length()];
    final int ans = maxRemovals(source, pattern, 0, 0, target, mem);
    return ans == Integer.MIN_VALUE ? 0 : ans;
  }

  // Returns the maximum number of operations that can be performed for
  // source[i..m) and pattern[j..n).
  private int maxRemovals(String source, String pattern, int i, int j, Set<Integer> target,
                          Integer[][] mem) {
    if (i == source.length())
      return j == pattern.length() ? 0 : Integer.MIN_VALUE;
    if (j == pattern.length())
      return (target.contains(i) ? 1 : 0) + maxRemovals(source, pattern, i + 1, j, target, mem);
    if (mem[i][j] != null)
      return mem[i][j];
    final int pick = source.charAt(i) == pattern.charAt(j)
                         ? maxRemovals(source, pattern, i + 1, j + 1, target, mem)
                         : Integer.MIN_VALUE;
    final int skip =
        (target.contains(i) ? 1 : 0) + maxRemovals(source, pattern, i + 1, j, target, mem);
    return mem[i][j] = Math.max(pick, skip);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
  def maxRemovals(
      self,
      source: str,
      pattern: str,
      targetIndices: list[int]
  ) -> int:
    m = len(source)
    n = len(pattern)
    target = set(targetIndices)

    @functools.lru_cache(None)
    def dp(i: int, j: int) -> int:
      """
      Returns the maximum number of operations that can be performed for
      source[i..m) and pattern[j..n).
      """
      if i == m:
        return 0 if j == n else -math.inf
      if j == n:
        return int(i in target) + dp(i + 1, j)
      pick = dp(i + 1, j + 1) if source[i] == pattern[j] else -math.inf
      skip = int(i in target) + dp(i + 1, j)
      return max(pick, skip)

    ans = dp(0, 0)
    return 0 if ans == -math.inf else ans

Approach 2: Bottom-up 2D DP

  • Time: $O(mn)$
  • Space: $O(mn)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int maxRemovals(string source, string pattern, vector<int>& targetIndices) {
    const int m = source.length();
    const int n = pattern.length();
    const unordered_set<int> target{targetIndices.begin(), targetIndices.end()};
    // dp[i][j] := the maximum number of operations that can be performed for
    // source[i..m) and pattern[j..n)
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MIN));
    dp[m][n] = 0;

    for (int i = m - 1; i >= 0; --i) {
      dp[i][n] = (target.contains(i) ? 1 : 0) + dp[i + 1][n];
      for (int j = n - 1; j >= 0; --j) {
        const int pick = source[i] == pattern[j] ? dp[i + 1][j + 1] : INT_MIN;
        const int skip = (target.contains(i) ? 1 : 0) + dp[i + 1][j];
        dp[i][j] = max(pick, skip);
      }
    }

    return dp[0][0] == INT_MIN ? 0 : dp[0][0];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public int maxRemovals(String source, String pattern, int[] targetIndices) {
    final int m = source.length();
    final int n = pattern.length();
    Set<Integer> target = Arrays.stream(targetIndices).boxed().collect(Collectors.toSet());
    // dp[i][j] := the maximum number of operations that can be performed for
    // source[i..m) and pattern[j..n)
    int[][] dp = new int[m + 1][n + 1];
    Arrays.stream(dp).forEach(A -> Arrays.fill(A, Integer.MIN_VALUE));
    dp[m][n] = 0;

    for (int i = m - 1; i >= 0; --i) {
      dp[i][n] = (target.contains(i) ? 1 : 0) + dp[i + 1][n];
      for (int j = n - 1; j >= 0; --j) {
        final int pick =
            source.charAt(i) == pattern.charAt(j) ? dp[i + 1][j + 1] : Integer.MIN_VALUE;
        final int skip = (target.contains(i) ? 1 : 0) + dp[i + 1][j];
        dp[i][j] = Math.max(pick, skip);
      }
    }

    return dp[0][0] == Integer.MIN_VALUE ? 0 : dp[0][0];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def maxRemovals(
      self,
      source: str,
      pattern: str,
      targetIndices: list[int]
  ) -> int:
    m = len(source)
    n = len(pattern)
    target = set(targetIndices)
    # dp[i][j] := the maximum number of operations that can be performed for
    # source[i..m) and pattern[j..n)
    dp = [[-math.inf] * (n + 1) for _ in range(m + 1)]
    dp[m][n] = 0

    for i in reversed(range(m)):
      dp[i][n] = int(i in target) + dp[i + 1][n]
      for j in reversed(range(n)):
        pick = dp[i + 1][j + 1] if source[i] == pattern[j] else -math.inf
        skip = int(i in target) + dp[i + 1][j]
        dp[i][j] = max(pick, skip)

    return 0 if dp[0][0] == -math.inf else dp[0][0]

Approach 3: Bottom-up 1D DP

  • Time: $O(mn)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  int maxRemovals(string source, string pattern, vector<int>& targetIndices) {
    const int m = source.length();
    const int n = pattern.length();
    const unordered_set<int> target{targetIndices.begin(), targetIndices.end()};
    // dp[j] := the maximum number of operations that can be performed for
    // source so far and pattern[j..n)
    vector<int> dp(n + 1, INT_MIN);
    dp[n] = 0;

    for (int i = m - 1; i >= 0; --i) {
      vector<int> newDp(dp);
      newDp[n] = (target.contains(i) ? 1 : 0) + dp[n];
      for (int j = n - 1; j >= 0; --j) {
        const int pick = source[i] == pattern[j] ? dp[j + 1] : INT_MIN;
        const int skip = (target.contains(i) ? 1 : 0) + dp[j];
        newDp[j] = max(pick, skip);
      }
      dp = std::move(newDp);
    }

    return dp[0] == INT_MIN ? 0 : dp[0];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
  public int maxRemovals(String source, String pattern, int[] targetIndices) {
    final int m = source.length();
    final int n = pattern.length();
    Set<Integer> target = Arrays.stream(targetIndices).boxed().collect(Collectors.toSet());
    // dp[j] := the maximum number of operations that can be performed for
    // source so far and pattern[j..n)
    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MIN_VALUE);
    dp[n] = 0;

    for (int i = m - 1; i >= 0; --i) {
      int[] newDp = dp.clone();
      newDp[n] = (target.contains(i) ? 1 : 0) + dp[n];
      for (int j = n - 1; j >= 0; --j) {
        final int pick = source.charAt(i) == pattern.charAt(j) ? dp[j + 1] : Integer.MIN_VALUE;
        final int skip = (target.contains(i) ? 1 : 0) + dp[j];
        newDp[j] = Math.max(pick, skip);
      }
      dp = newDp;
    }

    return dp[0] == Integer.MIN_VALUE ? 0 : dp[0];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
  def maxRemovals(
      self,
      source: str,
      pattern: str,
      targetIndices: list[int]
  ) -> int:
    m = len(source)
    n = len(pattern)
    target = set(targetIndices)
    # dp[j] := the maximum number of operations that can be performed for
    # source so far and pattern[j..n)
    dp = [-math.inf] * (n + 1)
    dp[n] = 0

    for i in reversed(range(m)):
      newDp = dp[:]
      newDp[n] = int(i in target) + dp[n]
      for j in range(n):
        pick = dp[j + 1] if source[i] == pattern[j] else -math.inf
        skip = int(i in target) + dp[j]
        newDp[j] = max(pick, skip)
      dp = newDp

    return 0 if dp[0] == -math.inf else dp[0]