Given a string S, you have to write the same given string using two operations, the task is to find the minimum number of operations to write it.
- You can only write a sequence of the same character each time.
- You can choose any substring and overwrite the existing characters with single new characters.
Examples:
Input: s = “aaaddd”
Output: 2
Explanation: Write “aaa” first and then write “ddd”.Input: s = “aca”
Output: 2
Explanation: Write “aaa” first and then write “c” from the second place of the string, which will cover the existing character ‘a’.
Minimizing Operations to Rewrite a String using Dynamic Programming.
This problem is easier to solve if we reduce it to subproblems using Divide and Conquer. We can break it down into smaller subproblems, we keep dividing s until the substring contains 1 or 2 characters (as the base case). We’ll define a DP table dp, where dp[i][j] will represent the minimum number of operations needed to write the substring s[i…j] (inclusive).
Base Case:For a single character (substring of length 1), we need only one operation to write it. Therefore, dp[i][i] = 1 for all i.
Recursive Formula: Now, we need to find the minimum number of operations for substrings of length 2, 3, and so on, up to the entire string length.
- For each substring length, we’ll iterate over all possible starting points (i) and ending points (j) of that substring.
- To compute dp[i][j], we’ll iterate over all possible k from i to j-1 (inclusive).
- For each k, we’ll try to find the minimum number of operations by combining the minimum operations required to write s[i…k] and s[k+1…j].
Final Answer: The answer to the problem will be stored in dp[0][n-1], where n is the length of the string.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <climits>#include <iostream>#include <vector>using namespace std;int writeString(string s){ int n = s.length(); vector<vector<int> > dp(n, vector<int>(n, 0)); for (int i = n - 1; i >= 0; --i) { // Base case: writing one character // always takes 1 operation. // Example: 'a' -> 1 operation dp[i][i] = 1; for (int j = i + 1; j < n; ++j) { dp[i][j] = INT_MAX; // Iterate through partition points k for (int k = i; k < j; ++k) { // Calculate the minimum operations // for writing s[i...k] and s[k+1...j] int minOperations = dp[i][k] + dp[k + 1][j]; // If s[i] and s[j] are the same, // we need one less turn because // we can write both characters // in a single operation only. if (s[i] == s[j]) minOperations--; // Example: 'aabaa' -> // Operations req: 2 // instead of 3 // Update dp[i][j] with the minimum // operations for s[i...j] dp[i][j] = min(dp[i][j], minOperations); } } } // Minimum operation for writing the entire // string s[0...n-1] return dp[0][n - 1];}// Drivers codeint main(){ string s = "aabca"; // Function Call cout << writeString(s); return 0;} |
3
Time Complexity: O(n^3), where n is length of given string.
Auxiliary Space: O(n*n)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
