Code :- class Solution { public: vector dp; // DP table to store results of subproblems // Recursive function to solve the problem for substring s[i...j] int solve(string &s, int i, int j) { // Base case: If the substring is of length 1, only 1 turn is needed if (i == j) return 1; // Return the stored result if it has been computed before if (dp[i][j] != -1) return dp[i][j]; int minTurn = INT_MAX; // Initialize minimum turns to a large value // Try every possible partition point k in the substring for (int k = i; k < j; k++) { // Calculate the minimum turns for the left and right parts of the partition int LeftPart = solve(s, i, k); int RightPart = solve(s, k + 1, j); // Update the minimum turns needed considering this partition minTurn = min(minTurn, LeftPart + RightPart); } // If characters at the start and end of the substring are the same, reduce the count by 1 return dp[i][j] = (s[i] == s[j]) ? minTurn - 1 : minTurn; } // Main function to calculate the minimum number of turns needed for the entire string int strangePrinter(string s) { int n = s.size(); // Initialize the DP table with -1, indicating that no subproblem has been solved yet dp.resize(n + 1, vector(n + 1, -1)); // Compute the result for the entire string from index 0 to n-1 return solve(s, 0, n - 1); } };
Code :-
class Solution {
public:
vector dp; // DP table to store results of subproblems
// Recursive function to solve the problem for substring s[i...j]
int solve(string &s, int i, int j) {
// Base case: If the substring is of length 1, only 1 turn is needed
if (i == j) return 1;
// Return the stored result if it has been computed before
if (dp[i][j] != -1) return dp[i][j];
int minTurn = INT_MAX; // Initialize minimum turns to a large value
// Try every possible partition point k in the substring
for (int k = i; k < j; k++) {
// Calculate the minimum turns for the left and right parts of the partition
int LeftPart = solve(s, i, k);
int RightPart = solve(s, k + 1, j);
// Update the minimum turns needed considering this partition
minTurn = min(minTurn, LeftPart + RightPart);
}
// If characters at the start and end of the substring are the same, reduce the count by 1
return dp[i][j] = (s[i] == s[j]) ? minTurn - 1 : minTurn;
}
// Main function to calculate the minimum number of turns needed for the entire string
int strangePrinter(string s) {
int n = s.size();
// Initialize the DP table with -1, indicating that no subproblem has been solved yet
dp.resize(n + 1, vector(n + 1, -1));
// Compute the result for the entire string from index 0 to n-1
return solve(s, 0, n - 1);
}
};
Good explanation
Thank you ❤️❤️
Very Well Explained Bro👍
Thank you ❤️
nice one
Thank you ❤️
TLE
it's Accepted ✨ Check again ...
Bhaiya ye pahle aapne 10^8 karke kaise complexity bataya next problem jab karana to please acche se samjhana bhaiya
Ok sure, I'll make sure to explain it clearly next time.
Thanks for the feedback! ✨❤️