Find the minimum cost of partitioning the given string S into contiguous substrings
Given a string S and an array of strings arr[]. The task is to find the minimum cost of partitioning the given string S into continuous substrings. If a substring is present in arr[] then the cost of partition would be 0, otherwise, the cost would be the length of that substring.
Examples:
Input: S = w3wiki, A[] = {geek, for}
Output: 2
Explanation: The explanation is as follows:
- Break w3wiki as {geek + s + for + geek+ s}
- 1st substring: “geek” is present in A[]. Therefore, cost is 0.
- 2nd substring: “s” is not present in A[]. Therefore, cost is 1.
- 3rd substring: “for” is present in A[]. Therefore, cost is 0.
- 4th substring: “geek” is present in A[]. Therefore, cost is 0.
- 5th substring: “s” is not present in A[]. Therefore, cost is 1.
- Total cost = 0+1+0+0+1 = 2. Which is minimum possible.
Input: S = BeginnerBeginner, A[] = {ge, ek, s, eeksBeginner},
Output: 0
Explanation: S can be broken in two ways {g + eeksBeginner} and {ge + ek + s + ge + ek + s} with cost 1 and 0 respectively. 0 is minimum possible cost.
Approach: Implement the idea below to solve the problem
As we have choice to delete or not delete a substring. Therefore, Dynamic Programming can be used to solve this problem. The main concept of DP in the problem will be:
- DP[i] will store the minimum cost of breaking string S till ith character.
- Transition:
- DP[i] = min(DP[i + 1] + 1, DP[i + e.size()]) for every ‘e’ where, e is string from array A[] and substring of string S starting from i is equal to string e.
Step-by-step approach:
- Declaring variable let say SizeOfS for storing size of S.
- Declaring DP[] array of length (SizeOfS + 1).
- Set base case as DP[SizeOfS] = 0.
- Calculating answer for ith state by iterating from i = (SizeOfS – 1) to 0 and follow below-mentioned steps:
- Set DP[i] with DP[i + 1] + 1
- Iterate in array arr[] as posSubstrToDelete
- If substring starting from ith index is equal to posSubstrToDelete, then:
- Update DP[i] as min(DP[i], DP[i + posSubstrToDelete.size()])
- If substring starting from ith index is equal to posSubstrToDelete, then:
- Return DP[0].
Below is the implementation of the above approach:
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to Minimize cost of breaking string in
// continuous substring
int minimumCost(string& S, vector<string>& A, int N)
{
// size of string
int szeOfS = S.size();
// DP array initalized with infinity
vector<int> dp(szeOfS + 1, 1e9);
// base case
dp[szeOfS] = 0;
// size of string
for (int i = szeOfS - 1; i >= 0; i--) {
// if we dont delete i'th character
dp[i] = dp[i + 1] + 1;
// iterate over possible substrings that
// can be removed from S
for (auto& posSubstrToDelete : A) {
// if substring from i'th character is equal to
// e update the dp array by deleting this
// substring
if (i + posSubstrToDelete.size() <= szeOfS
and S.substr(i, posSubstrToDelete.size())
== posSubstrToDelete) {
dp[i]
= min(dp[i],
dp[i + posSubstrToDelete.size()]);
}
}
}
// Returing answer
return dp[0];
}
// Driver Code
int32_t main()
{
// Input
string S1 = "w3wiki";
int N1 = 2;
vector<string> A1{ "geek", "for" };
// Function Call
cout << minimumCost(S1, A1, N1) << endl;
return 0;
}
// Java Implementation
import java.util.ArrayList;
import java.util.List;
public class MinimumCost {
public static int minimumCost(String S, List<String> A) {
int szeOfS = S.length();
int[] dp = new int[szeOfS + 1];
for (int i = 0; i <= szeOfS; i++) {
dp[i] = Integer.MAX_VALUE;
}
dp[szeOfS] = 0;
for (int i = szeOfS - 1; i >= 0; i--) {
dp[i] = dp[i + 1] + 1;
for (String posSubstrToDelete : A) {
if (i + posSubstrToDelete.length() <= szeOfS && S.substring(i, i + posSubstrToDelete.length()).equals(posSubstrToDelete)) {
dp[i] = Math.min(dp[i], dp[i + posSubstrToDelete.length()]);
}
}
}
return dp[0];
}
public static void main(String[] args) {
String S1 = "w3wiki";
int N1 = 2;
List<String> A1 = new ArrayList<>();
A1.add("geek");
A1.add("for");
System.out.println(minimumCost(S1, A1));
}
}
// This code is contributed by Tapesh(tapeshdu420)
using System;
using System.Collections.Generic;
class Program
{
// Function to Minimize cost of breaking string in continuous substring
static int MinimumCost(string S, List<string> A, int N)
{
// size of string
int szeOfS = S.Length;
// DP array initialized with infinity
List<int> dp = new List<int>(new int[szeOfS + 1]);
for (int i = 0; i < dp.Count; i++)
{
dp[i] = int.MaxValue;
}
// base case
dp[szeOfS] = 0;
// size of string
for (int i = szeOfS - 1; i >= 0; i--)
{
// if we don't delete i'th character
dp[i] = dp[i + 1] + 1;
// iterate over possible substrings that can be removed from S
foreach (var posSubstrToDelete in A)
{
// if substring from i'th character is equal to e update the dp array by deleting this substring
if (i + posSubstrToDelete.Length <= szeOfS
&& S.Substring(i, posSubstrToDelete.Length) == posSubstrToDelete)
{
dp[i] = Math.Min(dp[i], dp[i + posSubstrToDelete.Length]);
}
}
}
// Returning answer
return dp[0];
}
// Driver Code
static void Main()
{
// Input
string S1 = "w3wiki";
int N1 = 2;
List<string> A1 = new List<string> { "geek", "for" };
// Function Call
Console.WriteLine(MinimumCost(S1, A1, N1));
}
}
// This code is contributed by shivamgupta310570
// Function to minimize cost of breaking string in continuous substring
function minimumCost(S, A, N) {
// Size of string
const szeOfS = S.length;
// DP array initialized with infinity
const dp = new Array(szeOfS + 1).fill(1e9);
// Base case
dp[szeOfS] = 0;
// Size of string
for (let i = szeOfS - 1; i >= 0; i--) {
// If we don't delete i'th character
dp[i] = dp[i + 1] + 1;
// Iterate over possible substrings that can be removed from S
for (let posSubstrToDelete of A) {
// If substring from i'th character is equal to posSubstrToDelete
// Update the dp array by deleting this substring
if (i + posSubstrToDelete.length <= szeOfS &&
S.substring(i, i + posSubstrToDelete.length) === posSubstrToDelete) {
dp[i] = Math.min(dp[i], dp[i + posSubstrToDelete.length]);
}
}
}
// Returning answer
return dp[0];
}
// Driver Code
// Input
let S1 = "w3wiki";
let N1 = 2;
let A1 = ["geek", "for"];
// Function Call
console.log(minimumCost(S1, A1, N1));
// This code is contributed by shivamgupta310570
def minimum_cost(S, A, N):
# size of string
sze_of_S = len(S)
# DP array initialized with infinity
dp = [float('inf')] * (sze_of_S + 1)
# base case
dp[sze_of_S] = 0
# size of string
for i in range(sze_of_S - 1, -1, -1):
# if we don't delete i'th character
dp[i] = dp[i + 1] + 1
# iterate over possible substrings that
# can be removed from S
for pos_substr_to_delete in A:
# if substring from i'th character is equal to
# e update the dp array by deleting this
# substring
if (
i + len(pos_substr_to_delete) <= sze_of_S
and S[i:i + len(pos_substr_to_delete)] == pos_substr_to_delete
):
dp[i] = min(dp[i], dp[i + len(pos_substr_to_delete)])
# Returning answer
return dp[0]
# Driver Code
if __name__ == "__main__":
# Input
S1 = "w3wiki"
N1 = 2
A1 = ["geek", "for"]
# Function Call
print(minimum_cost(S1, A1, N1))
Output
2
Time Complexity: O(N*M*K), where N, M, K are length of string, length of A[] and maximum size of string among all strings from A[] respectively.
Auxiliary Space: O(N)
Contact Us