title: Delete all ocurrences of substring in minimal steps
body: <p>I want to find the minimum number of deletions I need to make in order for a substring to no longer appear in a given string. Both the string and substring are composed of only lower case letters.</p>
  
  <p>For example, for string "recorerecore" and substring "recore" I would need 2 deletions.</p>
  
  <p>For string "recorecore" and substring "recore" I would need only 1.</p>
  
  <p>For string "recorecorecorecore" and substring "recore" I would need 2, either the first and third or the second and fourth.</p>
  
  <p>For string "rerecorecore" I would need to take out 1, the second occurrence, as taking the first out would lead to having recore again.</p>
  
  <p>I only can think of the brute force solution which involves actually deleting in every combination possible and finding the minimum, but this takes too long.</p>
  
  <p>Does anyone know a way to do this faster?</p>