Leetcode Daily Question 23/09/2024 - 2707. Extra Characters in a String

Problem Description:

You are given a 0-indexed string s and a dictionary of words dictionary. You have to break s into one or more non-overlapping substrings such that each substring is present in dictionary. There may be some extra characters in s which are not present in any of the substrings. Return the minimum number of extra characters left over if you break up s optimally.

from typing import List
class Solution:
  def minExtraChar(self, s: str, dictionary: List[int]) -> int:
    n = len(s)
    dp = [float('inf')] * (n + 1)
    dp[n] = 0
    set_d = set(dictionary)
    
    
    for i in range(n - 1, -1, -1):
      dp[i] = 1 + dp[i+1]
      for j in range(i + 1, n + 1):
        if s[i:j] in words :
          dp[i] = min(dp[i],dp[j])
          
    return dp[0]

Explanation:

We can solve this using dp. The idea is to consider the shortest possible substring then build up our solution. We can do this either from the start or from the end of the string.

I choose to start at the end. We begin by assuming that s[i:] does not form any valid word. So then dp[i] = dp[i+1] + 1 as we added one extra character.

Then we search through s[i:]. If we find a j > i such that s[i:j] is in dictionary. Then we have dp[i] = min(dp[i],dp[j]) (since dp[j:]) is already solved).

In the end, dp[0] will tell us the answer.

We can also make dictionary into a set to make the look up O(1).

def minExtraChar(s, dictionary):
  n = len(s)
  dp = [float('inf')] * (n+1)
  dp[n] = 0 # We start by considering no character.
  set_d = set(dictionary) # Makes lookup of words O(1)
  
  for i in range(n - 1, -1, -1):
    dp[i] = dp[i + 1] + 1 # Assume s[i:] does not form valid word
    for j in range(i + 1, n + 1):
      if s[i:j] in set_d:
        dp[i] = min(dp[i], dp[j]) 
  
  return dp[0]

The time complexity is O(n^2) since we traverse the string backwards once and forwards n times, once for each iteration.

The space complexity is O(n) since we store the state for each possible substring from the end.

The full solution can be found near the top of the page.