My Solution
class Solution {
public:
int minExtraChar(string s, vector<string>& d) {
int n = s.size();
vector<int> f(n + 1);
for (int i = 0; i < n; i++) {
string t;
for (int k = i; k < n; k++) {
t += s[k];
for (int r = 0; r < d.size(); r++) {
if (t == d[r]) {
f[i]++, f[k + 1]--;
}
}
}
}
for (int i = 0; i < n; i++) {
f[i + 1] += f[i];
}
int ans = 0;
for (int i = 0; i < n; i++) {
if (f[i] == 0) ans += 1;
}
return ans;
}
};
1964/2028 test cases have been accepted. Below is one of the test cases in which my code gives a wrong output:
Testcase
s = "kevlplxozaizdhxoimmraiakbak",
d = ["yv","bmab","hv","bnsll","mra","jjqf","g","aiyzi","ip","pfctr","flr","ybbcl","biu","ke","lpl","iak","pirua","ilhqd","zdhx","fux","xaw","pdfvt","xf","t","wq","r","cgmud","aokas","xv","jf","cyys","wcaz","rvegf","ysg","xo","uwb","lw","okgk","vbmi","v","mvo","fxyx","ad","e"],
Expected Answer: 9,
My output: 8
I think it's easier to solve using a Trie
You missed the non-overlapping constraint.
Oh, I am so silly. Thank you!