Given two strings str1 and str2, the task is to find the minimum number of prefixes and suffixes of str2 required to form the string str1. If the task is not possible, return “-1”.
Example:
Input: str1 = “HELLOWORLD”, str2 = “OWORLDHELL”
Output: 2
Explanation: The above string can be formed as “HELL” + “OWORLD” which are suffix and prefix of the string str2Input: str = “GEEKSFORGEEKS”, wrd = “SFORGEEK”
Output: 3
Explanation: “GEEK” + “SFORGEEK” + “S”
Approach: The above problem can be solved using dynamic programming. Follow the steps below to solve the problem:
- Initialize an array dp where the ith element arr[i] will store the minimum concatenation required to form a string up to prefix index i
- Initialize dp[0] = 0 and other values of the dp array to -1
- Initialize a HashSet set
- Iterate the string str1 from left to right and at every index i:
- Add the substring from index 0 to current index i into the HashSet set
- Iterate the string str1 from right to left and at every index i:
- Add the substring from index i to the end index into the HashSet set
- Check for all the substrings in the string str1 and update the dp, accordingly
- The final answer will be stored in dp[N], where N is the length of string str1
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum number of// concatenation of prefix and suffix// of str2 to make str1int partCount(string str1, string str2){ // Initialize a set unordered_set<string> set; // Initialize a temporary string string temp = ""; int l1 = str1.length(), l2 = str2.length(); // Iterate the string str2 // from left to right for (int i = 0; i < l2; i++) { // Add current character // to string temp temp += str2[i]; // Insert the prefix into hashset set.insert(temp); } // Re-initialize temp string // to empty string temp = ""; // Iterate the string in reverse direction for (int i = l2 - 1; i >= 0; i--) { // Add current character to temp temp += str2[i]; // Reverse the string temp reverse(temp.begin(), temp.end()); // Insert the suffix into the hashset set.insert(temp); // Reverse the string temp again reverse(temp.begin(), temp.end()); } // Initialize dp array to store the answer int dp[str1.length() + 1]; memset(dp, -1, sizeof(dp)); dp[0] = 0; // Check for all substrings starting // and ending at every indices for (int i = 0; i < l1; i++) { for (int j = 1; j <= l1 - i; j++) { // HashSet contains the substring if (set.count(str1.substr(i, j))) { if (dp[i] == -1) { continue; } if (dp[i + j] == -1) { dp[i + j] = dp[i] + 1; } else { // Minimum of dp[i + j] and // dp[i] + 1 will be stored dp[i + j] = min(dp[i + j], dp[i] + 1); } } } } // Return the answer return dp[str1.size()];}// Driver Codeint main(){ string str = "GEEKSFORGEEKS", wrd = "SFORGEEK"; // Print the string cout << partCount(str, wrd);} |
Java
// Java implementation for the above approachimport java.util.Arrays;import java.util.HashSet;class GFG { // Function to find minimum number of // concatenation of prefix and suffix // of str2 to make str1 public static int partCount(String str1, String str2) { // Initialize a set HashSet<String> set = new HashSet<String>(); // Initialize a temporary string String temp = ""; int l1 = str1.length(), l2 = str2.length(); // Iterate the string str2 // from left to right for (int i = 0; i < l2; i++) { // Add current character // to string temp temp += str2.charAt(i); // Insert the prefix into hashset set.add(temp); } // Re-initialize temp string // to empty string temp = ""; // Iterate the string in reverse direction for (int i = l2 - 1; i >= 0; i--) { // Add current character to temp temp += str2.charAt(i); // Reverse the string temp temp = new StringBuffer(temp).reverse().toString(); // Insert the suffix into the hashset set.add(temp); // Reverse the string temp again temp = new StringBuffer(temp).reverse().toString(); } // Initialize dp array to store the answer int[] dp = new int[str1.length() + 1]; Arrays.fill(dp, -1); dp[0] = 0; // Check for all substrings starting // and ending at every indices for (int i = 0; i < l1; i++) { for (int j = 1; j <= l1 - i; j++) { // HashSet contains the substring if (set.contains(str1.substring(i, i + j))) { if (dp[i] == -1) { continue; } if (dp[i + j] == -1) { dp[i + j] = dp[i] + 1; } else { // Minimum of dp[i + j] and // dp[i] + 1 will be stored dp[i + j] = Math.min(dp[i + j], dp[i] + 1); } } } } // Return the answer return dp[str1.length()]; } // Driver Code public static void main(String args[]) { String str = "GEEKSFORGEEKS", wrd = "SFORGEEK"; // Print the string System.out.println(partCount(str, wrd)); }}// This code is contributed by gfgking. |
Python3
# Python3 implementation for the above approach# Function to find minimum number of# concatenation of prefix and suffix# of str2 to make str1def partCount(str1, str2): # Initialize a set se = set() # Initialize a temporary string temp = "" l1 = len(str1) l2 = len(str2) # Iterate the string str2 # from left to right for i in range(0, l2): # Add current character # to string temp temp += str2[i] # Insert the prefix into hashset se.add(temp) # Re-initialize temp string # to empty string temp = [] # Iterate the string in reverse direction for i in range(l2 - 1, -1, -1): # Add current character to temp temp.append(str2[i]) # Reverse the string temp temp.reverse() # Insert the suffix into the hashset se.add(''.join(temp)) # Reverse the string temp again temp.reverse() # Initialize dp array to store the answer dp = [-1 for _ in range(len(str1) + 1)] dp[0] = 0 # Check for all substrings starting # and ending at every indices for i in range(0, l1, 1): for j in range(1, l1 - i + 1): # HashSet contains the substring if (str1[i:i+j] in se): if (dp[i] == -1): continue if (dp[i + j] == -1): dp[i + j] = dp[i] + 1 else: # Minimum of dp[i + j] and # dp[i] + 1 will be stored dp[i + j] = min(dp[i + j], dp[i] + 1) # Return the answer return dp[len(str1)]# Driver Codeif __name__ == "__main__": str = "GEEKSFORGEEKS" wrd = "SFORGEEK" # Print the string print(partCount(str, wrd)) # This code is contributed by rakeshsahni |
C#
// C# implementation for the above approachusing System;using System.Collections.Generic;class GFG{ public static string Reverse(string Input) { // Converting string to character array char[] charArray = Input.ToCharArray(); // Declaring an empty string string reversedString = String.Empty; // Iterating the each character from right to left for(int i = charArray.Length - 1; i > -1; i--) { // Append each character to the reversedstring. reversedString += charArray[i]; } // Return the reversed string. return reversedString; } // Function to find minimum number of // concatenation of prefix and suffix // of str2 to make str1 public static int partCount(string str1, string str2) { // Initialize a set HashSet<String> set = new HashSet<String>(); // Initialize a temporary string string temp = ""; int l1 = str1.Length, l2 = str2.Length; // Iterate the string str2 // from left to right for (int i = 0; i < l2; i++) { // Add current character // to string temp temp += str2[i]; // Insert the prefix into hashset set.Add(temp); } // Re-initialize temp string // to empty string temp = ""; // Iterate the string in reverse direction for (int i = l2 - 1; i >= 0; i--) { // Add current character to temp temp += str2[i]; // Reverse the string temp temp = Reverse(temp); // Insert the suffix into the hashet set.Add(temp); // Reverse the string temp again temp = Reverse(temp); } // Initialize dp array to store the answer int[] dp = new int[str1.Length + 1]; for(int j=0; j<dp.Length;j++) { dp[j] = -1; } dp[0] = 0; // Check for all substrings starting // and ending at every indices for (int i = 0; i < l1; i++) { for (int j = 1; j <= l1 - i; j++) { // HashSet contains the substring if (set.Contains(str1.Substring(i, j))) { if (dp[i] == -1) { continue; } if (dp[i + j] == -1) { dp[i + j] = dp[i] + 1; } else { // Minimum of dp[i + j] and // dp[i] + 1 will be stored dp[i + j] = Math.Min(dp[i + j], dp[i] + 1); } } } } // Return the answer return dp[str1.Length]; } // Driver code static public void Main(String[] args) { string str = "GEEKSFORGEEKS", wrd = "SFORGEEK"; // Print the string Console.WriteLine(partCount(str, wrd)); }}// This code is contributed by code_hunt. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find minimum number of // concatenation of prefix and suffix // of str2 to make str1 function partCount(str1, str2) { // Initialize a set let set = new Set(); // Initialize a temporary string let temp = ""; let l1 = str1.length, l2 = str2.length; // Iterate the string str2 // from left to right for (let i = 0; i < l2; i++) { // Add current character // to string temp temp = temp + str2.charAt(i); // Insert the prefix into hashset set.add(temp); } // Re-initialize temp string // to empty string temp = ""; // Iterate the string in reverse direction for (let i = l2 - 1; i >= 0; i--) { // Add current character to temp temp = temp + str2.charAt(i); // Reverse the string temp temp = temp.split('').reduce((r, c) => c + r, ''); // Insert the suffix into the hashset set.add(temp); // Reverse the string temp again temp = temp.split('').reduce((r, c) => c + r, ''); } // Initialize dp array to store the answer let dp = new Array(str1.length + 1).fill(-1); dp[0] = 0; // Check for all substrings starting // and ending at every indices for (let i = 0; i < l1; i++) { for (let j = 1; j <= l1 - i; j++) { // HashSet contains the substring if (set.has(str1.substring(i, j))) { if (dp[i] == -1) { continue; } if (dp[i + j] == -1) { dp[i + j] = dp[i] + 1; } else { // Minimum of dp[i + j] and // dp[i] + 1 will be stored dp[i + j] = Math.min(dp[i + j], dp[i] + 1); } } } } // Return the answer return dp[str1.length] + 1; } // Driver Code let str = "GEEKSFORGEEKS" let wrd = "SFORGEEK"; // Print the string document.write(partCount(str, wrd)); // This code is contributed by Potta Lokesh </script> |
Output
3
Time Complexity: O(N^2), where N is length of str1
Auxiliary Space: O(N^2)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
