Type it!
-1671190285.svg){kind=small}
Geek is extremely punctual but today even he is not feeling like doing his homework assignment. He must start doing it immediately in order to meet the deadline. For the assignment, Geek needs to type a string s.
To reduce his workload, he has decided to perform one of the following two operations till he gets the string.
- Append a character at the end of the string.
- Append the string formed thus far to the end of the string. (This can not be done more than once.)
Help Geek find the minimum operations required to type the given string.
Example 1:
Input:
s = abcabca
Output: 5
Explanation: a -> ab -> abc -> abcabc
-> abcabca
Example 2:
Input:
s = abcdefgh
Output: 8
Explanation: a -> ab -> abc -> abcd
-> abcde -> abcdef -> abcdefg -> abcdefgh
Your Task:
You don't need to read input or print anything. Your task is to complete the function minOperation() which takes a string s as input parameter and returns the minimum operations required to type it.
Expected Time Complexity: O(N2)
Expected Auxiliary Space: O(1)
Constraints:
1 <= N <= 103
Solution
class Solution {
public:
void rec(string& s,vector<int>& dp,int i){
if(i>=s.size()) return;
int res=INT_MAX;
if(i%2==1){
int h=i/2,t=i;
while(h>=0&&s[h]==s[t]) h--,t--;
if(h==-1) res=(i/2)+2;
}
if(i>0) res=min(res,dp[i-1]+1);
else res=1;
dp[i]=res;
rec(s,dp,i+1);
}
int minOperation(string& s) {
// code here
vector<int> dp(s.size(),-1);
// rec(s,dp,0); //for recursive solution
for(int i=0;i<s.size();i++){
int res=INT_MAX;
if(i%2==1){
int h=i/2,t=i;
while(h>=0&&s[h]==s[t]) h--,t--;
if(h==-1) res=(i/2)+2;
}
if(i>0) res=min(res,dp[i-1]+1);
else res=1;
dp[i]=res;
}
return dp[s.size()-1];
}
};
The above solution is attempting to solve the problem of finding the minimum number of operations required to make a given string a palindrome. It does this by using a dynamic programming approach, where it keeps track of the minimum number of operations required for each substring of the input string up to a certain index. The function minOperation(string &s) takes in a string as input and returns an integer representing the minimum number of operations required to make the input string a palindrome.
The function uses two helper variables, a vector dp of size s.size() and an integer i. The vector dp is used to store the minimum number of operations required for each substring of the input string up to index i. The integer i is used to iterate through the input string and check each substring.
The function uses two nested loops, one is recursive and another is iterative. The recursive loop rec(s,dp,i) starts from index 0 and increment one by one. In the each iteration it checks if the substring from index 0 to i is already a palindrome or not. If the substring is already a palindrome, it sets the value of dp[i] to (i/2)+2. If the substring is not a palindrome, it sets the value of dp[i] to the minimum of dp[i-1]+1 and res. It then calls the function recursively with the next index.
The iterative loop starts with i=0 and goes till the size of the string and it will check the substring from index 0 to i is already a palindrome or not. If the substring is already a palindrome, it sets the value of dp[i] to (i/2)+2. If the substring is not a palindrome, it sets the value of dp[i] to the minimum of dp[i-1]+1 and res.
Finally, the function returns the value of dp[s.size()-1], which represents the minimum number of operations required to make the input string a palindrome.
Comments
Post a Comment