PSTRING - Remove The String
Given two strings X and Y, your task is find the minimum number of characters to be removed from X in order to obtain a string X' that does not contain Y as a substring.
Input contains some test cases. Each test cases contains two lines, First is X and second is Y. Length of X <= 10000, Length of Y <= 1000.
For each test cases, You should output exactly one integer is the minimum number of characters to be remove
Input: ababaa aba Output: 1
Buda IM (retired):
O( |X|*|Y| ), is just fine using bottom up, recursion will TLE.
Jose Luis Castrillon Garrido:
O(length(X)*length(Y)) is getting TLE, is expected to implement another algorithm?
Isn't it bbaa?Last edit: 2014-10-17 16:51:26
If we remove the char 'c' from bbcaa, will the resulting string be bbaa or bb aa?