How to Approach?
Our first step should be to find all the xprime substrings because after that, only we can proceed to erase some characters to eliminate all the xprime substrings.
How to find all the xprime substrings?
We will see the brute force approach to do this.
The steps are as follows:
 Iterate over all the substrings of the string s.
 For each substring s[i,..j], check the sum of its digits.
 If the sum is equal to x, then proceed to check all of its substrings to find if there exists a substring of s[i,..j] such that its sum of digits is not equal to x, but it divides x. If so, then this means the current substring s[i,..j] is not xprime.
There are some important points that we can deduce by observing the constraints of the given problem, which is 1<=x<=20 and 1<=s<=1000 
 Since x can not be more than 20, the total count of xprime strings of any given string will be relatively small.
 If we consider the sum of the lengths of all the xprime strings, it will also be small and can be up to a maximum value of 5000.
Following the above two points, now our problem is 
 We have a string s having a maximum length of 1000 and a set of xprime strings whose total length is up to 5000.
 We have to erase a minimum number of characters from that string s such that none of the strings from the set of xprime strings appears as a substring of the resulting string s.
Now, how to solve this problem?
Whenever in any problem, we have to make some choices, and out of all possible choices we need to select the most optimal choice then this clearly points to using â€śDynamic Programmingâ€ť.
Letâ€™s see the DP approach in detail in the next section.
Dynamic Programming Approach
The steps of implementation of the DP approach are as follows:

Generate all the xprime strings for the integer x.

Build a trie of all the xprime strings to match their prefixes according to the ahocorasick algorithm.

Each vertex of the trie can be interpreted as a position in one or more strings from the xprime strings set.

Define a 2D dp[][] array with the number of rows=length of string s + 1 and the number of columns = size of trie constructed.

Initialize the dp array with INT_MAX.

The value dp[x][y] represents the minimum number of characters to be erased if we consider the first x characters of string s, and it does not consist of any of the strings from the set.

y is the length of the longest suffix of the current string that coincides with some prefix of a string from the set.

If there exists a string from the set, which is a suffix of y, then there is an occurrence of an xprime string.

Else, we don't have any xprime string ending in the last character because the longest possible suffix that matches some prefix from the set has been taken into account.
 So, summing up the transitions in dp, we have two choices: to take the next character and recompute or ignore the next character and increment the current number of characters to be erased by 1.
Note: After reading the Algorithm part, it is recommended to try writing the code on your own before reading the solution code.
Letâ€™s see the code implementation and the time and space complexity analysis in the next section.
Also check out  Substr C++
C++ Implementation
/*
C++ Program to Find the minimum number of characters you should
erase from the string so that there are no xprime substrings in it
*/
#include <bits/stdc++.h>
using namespace std;
const int AL = 9; // as the string only contains integers from 1 to 9
const int N = 5000;
const int INF = 1e9;
// defining node structure for the trie for Ahocorasick algorithm
struct node
{
int next[AL];
int p; // state
char pch;
int link;
int go[AL];
// bool term;
bool leaf = false;
node()
{
memset(next, 1, sizeof(next));
memset(go, 1, sizeof(go));
link = p = 1;
leaf = false;
}
int &operator[](int x)
{
return next[x];
}
};
string s;
string t;
int x;
/* Implementing Ahocorasick algorithm */
// creating the trie as a vector of the struture "nodes"
vector<node> trie;
// function to add a string s to the trie
void add_string(string s)
{
int v = 0;
for (char it : s)
{
int c = it  '1'; // '1'<=it<='9 so 0<=c<=8
if (trie[v][c] == 1)
{
trie.push_back(node());
trie[trie.size()  1].p = v;
trie[trie.size()  1].pch = c;
trie[v][c] = trie.size()  1;
}
v = trie[v][c];
}
trie[v].leaf = true;
}
int go(int v, int c);
int get_link(int v)
{
if (trie[v].link == 1)
{
if (v == 0  trie[v].p == 0)
trie[v].link = 0;
else
trie[v].link = go(get_link(trie[v].p), trie[v].pch);
}
return trie[v].link;
}
int go(int v, int c)
{
if (trie[v].go[c] == 1)
{
if (trie[v][c] != 1)
trie[v].go[c] = trie[v][c];
else
trie[v].go[c] = (v == 0 ? 0 : go(get_link(v), c));
}
return trie[v].go[c];
}
// function to generate all xprime strings
void generateAll_X_Prime_Strings(int i, int sum)
{
if (sum == x)
{
bool is_x_prime = true;
for (int l = 0; l < int(t.size()); ++l)
{
int cur = 0;
for (int r = l; r < int(t.size()); ++r)
{
cur += (t[r]  '0');
if (x % cur == 0 && cur != x)
is_x_prime = false;
}
}
if (is_x_prime)
{
add_string(t);
}
return;
}
for (int j = 1; j <= min(x  sum, 9); ++j)
{
t += '0' + j;
generateAll_X_Prime_Strings(i + 1, sum + j);
t.pop_back();
}
}
int main()
{
s = "116285317";
x = 8;
int minNumCharacters;
trie.push_back(node());
generateAll_X_Prime_Strings(0, 0);
vector<vector<int>> dp(s.size() + 1, vector<int>(trie.size(), INF));
dp[0][0] = 0;
for (int i = 0; i < s.size(); i++)
{
for (int j = 0; j < trie.size(); j++)
{
if (dp[i][j] != INF)
{
dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + 1);
int next = go(j, s[i]  '1');
//if by adding the next character we dont get a xprime string
if (!trie[next].leaf)
dp[i + 1][next] = min(dp[i + 1][next], dp[i][j]);
}
}
}
minNumCharacters = *min_element(dp[s.size()].begin(), dp[s.size()].end());
cout << "The minimum number of characters to be erased from the string = " << minNumCharacters << endl;
return 0;
}
Output
The minimum number of characters to be erased from the string = 2
Time Complexity
O(n*number_of_xPrime_strings), where nlength of the string s.
This is because we are using two nested loops, one of length n and the other of length equal to trie size, which in the worst case can be equal to the number of xPrime strings. Hence, the total time complexity is O(n*number_of_xPrime strings).
Space Complexity
We use a 2D dp array of size=(n*number_of_xPrime_strings) and a trie for the ahocorasick algorithm which uses O(alphabet_size * average key length * number_of_xPrime strings) space. Here alphabet_size is equal to 9 because the string only contains numbers from 1 to 9. Thus the total space complexity is O(n*number_of_xPrime_strings) + O(9 * average key length * number_of_xPrime strings).
Check out this problem  Frog Jump
Frequently Asked Questions

What is the proper prefix of a string?
The proper prefix of a string is a substring that is not equal to the length of the string itself.

What is a trie?
A trie is an ordered data structure, a search tree used to store associative data structures. It is also referred to as a Radix tree or Prefix tree.

Where can you use a trie?
You use a trie to take a partial value and return a set of possible complete values.

What is the AhoCorasick algorithm?
The AhoCorasick algorithm uses a trie data structure to match multiple patterns against a large sequence of text efficiently.

What is a string matching problem?
The problem of finding occurrence(s) of a pattern string within another string or body of text.
Key Takeaways
In this article, we learnt to solve the problem of an xprime substring by carefully observing the constraints given and crafting the approach to reach the optimal solution.
We used Trie, dynamic programming and the AhoCorasick algorithm to reach the solution.
To learn the concepts used in this article, check out the following articles
Recommended problems 
Are you planning to ace the interviews of reputed productbased companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!