This is our solution and implementation to problem #2186: Minimum Number of Steps to Make Two Strings Anagram II on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy a breakdown on the space and time complexity, and the full code implementation.
If you would like to view the original problem and solve it, please visit: Minimum Number of Steps to Make Two Strings Anagram II on LeetCode.
Problem Analysis
We need to make the two words anagrams of each other by appending characters. The problem states we can only append characters, not remove them. Therefore, we only need to determine which characters from each string are missing in the other string and how many. That count is equal to the number of steps it would take to make the two words anagrams of each other.
Implementation Strategy
We will use a map to track the number of letter differences between each word. Iterate over the chars of each string and keep track of how many times each letter occurs. We'll use a single hash map and increment the map count when a letter occurs in s and decrement when it occurs in t. Then, we'll take the absolute values of each count and return their sum.
Space and Time Complexity
The time complexity is O(s+t), as we iterate over each string once, then iterate up to s+t to get the char counts. The space complexity is O(s+t) as the map will have up to s+t chars.
Additional Resources
The links below outline some of the points discussed above in more detail.
Full Code
Our solution is given in the Java code below:
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.