Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Understanding the Problem
3.
Intuition
4.
Code
4.1.
Input
4.2.
Output
4.3.
Time Complexity
4.4.
Space Complexity
5.
Key Takeaways
Last Updated: Mar 27, 2024

Minimum Count of Prefixes and Suffixes of a String Required to Form Given String

Author Saksham Gupta
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

Dynamic programming is an all-time favorite topic when it comes to tech interviews, and solving its classical problems surely helps you to clear the basics. Today we will be seeing one such classical problem named ‘minimum count of prefixes and suffixes of a string required to form given string’ and will brush our concepts related to dynamic programming. Now without wasting any more time, let’s jump to the problem.

Also Read, Byte Array to String

Understanding the Problem

We have been given two strings, ‘S1’ and ‘S2’. Our task is to find the minimum number of prefixes and suffixes of ‘S2’  that are needed to form ‘S1’. If it’s not possible to form ‘S1’ then we will return ‘-1’.

Let’s understand the problem statement better by the following example.

‘S1’= codingninjas

‘S2’= ninjascoding

Output 

2

Explanation

Now, ‘S1’ can be formed by breaking ‘S2’ into two pieces, i.e., ninjas and coding, and then combining them as coding + ninjas to form ‘S1’.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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 -

 

Previous article
Maximum Product of Two Non-intersecting Paths in a Tree
Next article
Finding the Minimum Cost to Reduce the Array by Merging the Adjacent Elements Repetitively
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass