veryverydarkgray's blog

By veryverydarkgray, 10 years ago, In English

The task is to minimize the length of resulting string after repeatedly removing a given substring. Note that after removal, new occurrences of the substring may be formed.

Example:

Given string: aaababa

String to remove: aba

Possibilities:

  1. aaababa -> aaab

  2. aaababa -> aaba -> a

So in this case the answer is 1.

This looks like a standard problem but i am unable to solve it. An even tougher version of the problem appeared on: https://www.hackerrank.com/contests/apc/challenges/reducto where instead of a single string, a set of strings can be removed. Sadly, an editorial is not available.

Full text and comments »

  • Vote: I like it
  • +10
  • Vote: I do not like it