Solution 4 for Scaler Topics Fortnightly Contest - 22
FREE
Minimum Money Required Complete Solution
This article is part of the Scaler Topics Fortnightly Contest - 22
Build an AI-First Career, Master the Complete Skillset
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
AI Forward Deployed Engineer Program
Full-stack engineering, production AI and client-facing consulting
+1000 moreSolution Approach
The given problem requires converting string A to string B with minimum cost, where four types of operations are allowed: insertion, deletion, replacement, and swapping adjacent characters. Each operation has a specific cost associated with it.
To solve this problem, we can use dynamic programming to build an optimal solution incrementally. Let’s break down the approach:
Initialize variables:
- N and M are the lengths of strings A and B, respectively.
- Create a 2D dp array of size (N + 1) x (M + 1), where dp[i][j] represents the minimum cost to convert the substring A[0...i-1] to the substring B[0 ... j - 1].
- Create two arrays, pres and pret, of size 26 (representing the lowercase English alphabet) to store the last positions of characters encountered in A and B during the iteration.
- Initialize mi, md, mr, and me as the costs for insert, delete, replace, and swap operations, respectively.
Initialize base cases:
- Set dp[0][0] = 0, representing the cost of converting an empty string to another empty string.
- Initialize the cost of converting A to an empty string (deletion) by iterating from 1 to N: dp[i][0] = i * md.
- Initialize the cost of converting an empty string to B (insertion) by iterating from 1 to M: dp[0][j] = j * mi.
Perform the dynamic programming calculation:
- Iterate over i from 1 to N (representing the characters in A).
- Clear the pret array to store the last positions of characters encountered in B during this iteration.
- Iterate over j from 1 to M (representing the characters in B).
- Calculate the minimum cost of converting A[0...i-1] to B[0...j-1] by considering three possible operations: -- Deletion: dp[i][j] = dp[i - 1][j] + md. -- Insertion: dp[i][j] = dp[i][j - 1] + mi. -- Replacement: dp[i][j] = dp[i - 1][j - 1] if A[i - 1] == B[j - 1], otherwise dp[i][j] = dp[i - 1][j - 1] + mr.
- Check if swapping adjacent characters reduces the cost:
- Retrieve the last positions of the current characters from pres and pret arrays (indices k and l).
- If both k and l are non-zero (indicating the characters exist in both A and B), calculate the cost of swapping:
dp[i][j] = dp[k - 1][l - 1] + (i - k - 1) * md + (j - l - 1) * mi + me
- Update the pret array with the current position j for character B[j - 1].
Return the minimum cost: The final answer is stored in dp[N][M], representing the minimum cost to convert A to B.
This approach utilizes dynamic programming to calculate the minimum cost of converting A to B by considering all possible operations. By building the dp matrix iteratively, we ensure that the optimal cost is calculated for each substring. The time complexity of this solution is O(N * M), where N and M are the lengths of strings A and B, respectively.
C++ Implementation
Java Implementation
How Scaler Transformed Careers in Different Fields
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ more
