Minimum Number of Steps to Make Two Strings Anagram
MedPrompt
You are given two strings of the same length s and t. In one step you can choose any character of t and replace it with another character.
Return the minimum number of steps to make t an anagram of s.
An Anagram of a string is a string that contains the same characters with a different (or the same) ordering.
Example 1:
Input: s = "bab", t = "aba"
Output: 1
Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s.Example 2:
Input: s = "leetcode", t = "practice"
Output: 5
Explanation: Replace 'p', 'r', 'a', 'i' and 'c' from t with proper characters to make t anagram of s.Example 3:
Input: s = "anagram", t = "mangaar"
Output: 0
Explanation: "anagram" and "mangaar" are anagrams.
Constraints:
1 <= s.length <= 5 * 104s.length == t.lengthsandtconsist of lowercase English letters only.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves using a hash map to store the character frequencies of the target anagram string s. We then iterate through the string t and 'use up' the characters that match. The total count of characters remaining in the map represents the number of characters in s that were not present in t, which is exactly the number of replacements needed.
Algorithm
- Create a frequency map for all characters in string
susing a Hash Map. - Iterate through string
t. For each character, if it's in the frequency map and its count is positive, decrement the count. - The result is the sum of all remaining counts in the frequency map.
Walkthrough
To solve this problem, we first need to know the character composition of an anagram of s. We can achieve this by counting the frequency of each character in s and storing it in a hash map.
Once we have the frequency map for s, we can iterate through string t. For each character in t, we check if it's a character that s needs. If it is (i.e., it's in our map with a count greater than zero), we decrement its count in the map. This signifies that one character from t has successfully matched one required character for the anagram.
After checking all characters in t, the hash map will contain the counts of characters that are in s but were not matched by characters from t. The sum of these leftover counts gives the total number of characters that are 'missing' from t. Since each replacement operation can fix one missing character, this sum is the minimum number of steps required.
import java.util.HashMap;import java.util.Map; class Solution { public int minSteps(String s, String t) { Map<Character, Integer> sCounts = new HashMap<>(); for (char c : s.toCharArray()) { sCounts.put(c, sCounts.getOrDefault(c, 0) + 1); } // Decrement counts for characters present in t for (char c : t.toCharArray()) { if (sCounts.containsKey(c) && sCounts.get(c) > 0) { sCounts.put(c, sCounts.get(c) - 1); } } // Sum of remaining counts is the number of characters to change int steps = 0; for (int count : sCounts.values()) { steps += count; } return steps; }}Complexity
Time
O(N), where N is the length of the strings. We iterate through `s` once (O(N)), `t` once (O(N)), and the map's values once (O(K), where K <= 26). The total is O(N).
Space
O(K), where K is the number of unique characters in the alphabet. For lowercase English letters, K is at most 26, so the space is O(1).
Trade-offs
Pros
Conceptually simple and easy to implement.
Flexible enough to work with any character set, not just lowercase English letters.
Cons
Slightly less performant than an array-based approach due to the overhead of hash map operations (hashing, collision handling).
This approach improves upon the hash map method by using a simple array of size 26 as a frequency counter, which is possible because the input strings consist only of lowercase English letters. We calculate the net difference in character frequencies between s and t. The number of required changes is the sum of all characters that s has in excess compared to t.
Algorithm
- Initialize an integer array
countsof size 26 to all zeros. - Iterate through string
s, incrementing the count for each character. - Iterate through string
t, decrementing the count for each character. - Sum all the positive values in the
countsarray. This sum is the minimum number of steps.
Walkthrough
Given the constraint that strings only contain lowercase English letters, we can use a fixed-size array of 26 integers for frequency counting, which is more efficient than a hash map. Each index in the array corresponds to a letter from 'a' to 'z'.
The algorithm works by first populating this array with the character counts from string s. Then, it iterates through string t and decrements the counts for each character found. After these two passes, the array holds the difference in frequencies for each character between s and t. A positive value at counts[i] means s has more of character ('a' + i) than t, while a negative value means t has more.
The minimum number of steps is the number of characters we need to introduce into t to match s. This is precisely the sum of all positive counts in our final frequency array. Each positive count counts[i] represents a deficit of that character in t that needs to be filled by a replacement.
class Solution { public int minSteps(String s, String t) { int[] counts = new int[26]; for (char c : s.toCharArray()) { counts[c - 'a']++; } for (char c : t.toCharArray()) { counts[c - 'a']--; } int steps = 0; for (int count : counts) { if (count > 0) { steps += count; } } return steps; }}As a small optimization, since the string lengths are equal, the loops for s and t can be combined into one:
// Combined loop optimizationclass Solution { public int minSteps(String s, String t) { int[] counts = new int[26]; for (int i = 0; i < s.length(); i++) { counts[s.charAt(i) - 'a']++; counts[t.charAt(i) - 'a']--; } int steps = 0; for (int count : counts) { if (count > 0) { steps += count; } } return steps; }}Complexity
Time
O(N), where N is the length of the strings. We iterate through the strings to populate the frequency array (O(N)) and then iterate through the array of size 26 (O(1)). The total complexity is O(N).
Space
O(1), as the space used is a fixed-size array of 26 integers, which does not depend on the input string length.
Trade-offs
Pros
Extremely efficient in both time and space due to direct array indexing.
Simple to implement for a fixed, small character set.
Cons
The implementation is specific to the character set ('a'-'z') and would require changes for other character sets.
Solutions
Solution
/** * @param {string} s * @param {string} t * @return {number} */ var minSteps = function (s, t) { const cnt = new Array(26).fill(0); for (const c of s) { const i = c.charCodeAt(0) - " a ".charCodeAt(0); ++cnt[i]; } let ans = 0; for (const c of t) { const i = c.charCodeAt(0) - " a ".charCodeAt(0); ans += --cnt[i] < 0; } return ans; };class Solution {public int minSteps(String s, String t) { int[] cnt = new int[26]; for (int i = 0; i < s.length(); ++i) { ++cnt[s.charAt(i) - 'a']; } int ans = 0; for (int i = 0; i < t.length(); ++i) { if (--cnt[t.charAt(i) - 'a'] < 0) { ++ans; } } return ans; }}class Solution {public: int minSteps(string s, string t) { int cnt[26]{}; for (char &c : s) ++cnt[c - 'a']; int ans = 0; for (char &c : t) { ans += --cnt[c - 'a'] < 0; } return ans; }};class Solution: def minSteps(self, s: str, t: str) -> int: cnt = Counter(s) ans = 0 for c in t: if cnt[c] > 0: cnt[c] -= 1 else: ans += 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.