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 -
306+ registered