## Intuition

The intuition here is to use Dynamic Programming.

*But how?*

We will create an array â€˜DPâ€™ in which DP[i] will represent the minimum concatenation that is required to form a string up to prefix index â€˜iâ€™.

- Now dp[0] will be initialized to 0 as for no character the minimum concatenations that are required are also 0.
- Next, we will create a Hash Set which will store all the prefixes and suffixes of â€˜S2â€™. We can store that by first traversing string from left to right and then from right to left.
- Now we will start iterating over â€˜S1â€™ and check for all its substrings and update the â€˜DPâ€™ accordingly (Will be understood better by code).

Now letâ€™s look at the code for the above algorithm.

## Code

```
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;
// Function which will return the final answer.
int minCount(string s1, string s2)
{
unordered_set<string> preSuff;
// Initialize a temporary string
string temp = "";
int i = 0;
int len1 = s1.length();
int len2 = s2.length();
// First iterating from left to right.
while (i < len2)
{
temp += s2[i];
// Inserting into HashSet.
preSuff.insert(temp);
i++;
}
temp = "";
i = len2 - 1;
// Now iterating from right to left.
while (i >= 0)
{
temp += s2[i];
reverse(temp.begin(), temp.end());
// Insert into HashSet.
preSuff.insert(temp);
reverse(temp.begin(), temp.end());
i--;
}
// DP Array.
vector<int> dp(len1 + 1, -1);
dp[0] = 0;
// Checking all substrings.
for (int i = 0; i < len1; i++)
{
for (int j = 1; j <= len1 - i; j++)
{
// If there is a substring present in HashSet.
if (preSuff.count(s1.substr(i, j)))
{
if (dp[i] == -1)
{
continue;
}
if (dp[i + j] == -1)
{
dp[i + j] = dp[i] + 1;
}
else
{
dp[i + j] = min(dp[i + j], dp[i] + 1);
}
}
}
}
// Return the answer
return dp[len1];
}
// Driver Code
int main()
{
string s1, s2;
// Taking Input.
cin >> s1 >> s2;
cout << minCount(s1, s2);
}
```

### Input

```
codingninjas
ninjascoding
```

### Output

`2`

### Time Complexity

**O(N ^ 2)**, where â€˜Nâ€™ is the length of â€˜S1â€™.

Here we are first inserting prefix and suffix of string â€˜S2â€™ into Hash Set, which will cost us O(L2) time, where L2 is the length of string â€˜S2â€™. Then we are checking for substrings of â€˜S1â€™ using two nested loops which will cost us O(N ^ 2) time. So over time complexity would be-

O(L2 + N ^ 2) ~ O(N ^ 2).

### Space Complexity

**O(L2 ^ 2)**, where 'L2' is the length of â€˜S2â€™.

Since we are storing all the prefixes and suffixes of â€˜S2â€™ in an external hash set.

## Key Takeaways

We saw how we solved the problem â€˜Minimum count of prefixes and suffixes of a string required to form given stringâ€™ using Dynamic Programming, which refreshed your concepts about Hash Set. Now, there are many variations to these two concepts, but you donâ€™t have to worry about any of it when your ninja friend is here, so head over to our practice platform __Coding Ninjas Studio__ to practice top problems and many more. Till then, Happy Coding!

**Recommended problems -**