0% completed
Problem Statement
Given two strings, s
and t
, of the same length, return the minimum number of steps required to make t
an anagram of s
.
In each step, you can replace any character in t
with another character.
An anagram of a string is a string that contains the same characters in any order.
Examples
Example 1:
- Input: s = "designgurus", t = "garumdespgn"
- Expected Output: 3
- Justification: We need to replace
a
,m
, andp
characters in the stringt
to match the frequency of characters ins
.
Example 2:
- Input: s = "abc", t = "def"
- Expected Output: 3
- Justification: We need to replace all three characters in
t
to match those ins
.
Example 3:
- Input: s = "listen", t = "silent"
- Expected Output: 0
- Justification: The string
t
is already an anagram ofs
.
Constraints:
- 1 <= s.length <= 5 * 10<sup>4</sup>
s.length == t.length
s
andt
consist of lowercase English letters only.
Solution
To solve this problem, we use a HashMap
to keep track of the frequency differences between the characters in two strings, s
and t
. The idea is to increment the frequency count for each character in t
and decrement it for each character in s
. This will give us a map with the net frequency difference for each character. By summing up the positive differences, we can determine the minimum number of steps required to make t
an anagram of s
.
This method ensures that we efficiently count and compare character frequencies, making the solution both time-efficient and easy to implement.
Step-by-step Algorithm
-
Initialize Frequency Difference Map:
- Create a map to store the frequency difference of characters between the two strings. This map will help track how many characters need to be added or removed to make the strings anagrams of each other.
-
Count the Frequency Differences:
- For each character in the strings
s
andt
:- Increment the count for the character in
t
in the frequency difference map. - Decrement the count for the character in
s
in the frequency difference map. - This step helps identify the characters that are in excess or deficit in
t
compared tos
.
- Increment the count for the character in
- For each character in the strings
-
Calculate the Number of Steps Needed:
- Initialize a variable
steps
to 0. This will keep track of the number of characters that need to be replaced. - For each count in the frequency difference map:
- If the count is positive, add it to
steps
. This represents the characters int
that are in excess and need to be replaced to matchs
. In this step, the excess characters of strings
will be replaced by the excess characters of stringt
. So, we don't need to count them.
- If the count is positive, add it to
- Initialize a variable
-
Return the Result:
- Return the value of
steps
, which represents the minimum number of character replacements needed to maket
an anagram ofs
.
- Return the value of
Algorithm Walkthrough
Using the input:
- s = "designgurus"
- t = "garumdespgn"
-
Initialization:
frequencyDifference
= {}
-
Traverse both strings and update frequency differences:
- i = 0:
charT = 'g'
,charS = 'd'
- Increment frequency of 'g':
frequencyDifference.put('g', 1)
- Decrement frequency of 'd':
frequencyDifference.put('d', -1)
frequencyDifference
= {'g': 1, 'd': -1}
- i = 1:
charT = 'a'
,charS = 'e'
- Increment frequency of 'a':
frequencyDifference.put('a', 1)
- Decrement frequency of 'e':
frequencyDifference.put('e', -1)
frequencyDifference
= {'g': 1, 'd': -1, 'a': 1, 'e': -1}
- i = 2:
charT = 'r'
,charS = 's'
- Increment frequency of 'r':
frequencyDifference.put('r', 1)
- Decrement frequency of 's':
frequencyDifference.put('s', -1)
frequencyDifference
= {'g': 1, 'd': -1, 'a': 1, 'e': -1, 'r': 1, 's': -1}
- i = 3:
charT = 'u'
,charS = 'i'
- Increment frequency of 'u':
frequencyDifference.put('u', 1)
- Decrement frequency of 'i':
frequencyDifference.put('i', -1)
frequencyDifference
= {'g': 1, 'd': -1, 'a': 1, 'e': -1, 'r': 1, 's': -1, 'u': 1, 'i': -1}
- i = 4:
charT = 'm'
,charS = 'g'
- Increment frequency of 'm':
frequencyDifference.put('m', 1)
- Decrement frequency of 'g':
frequencyDifference.put('g', 0)
frequencyDifference
= {'g': 0, 'd': -1, 'a': 1, 'e': -1, 'r': 1, 's': -1, 'u': 1, 'i': -1, 'm': 1}
- i = 5:
charT = 'd'
,charS = 'n'
- Increment frequency of 'd':
frequencyDifference.put('d', 0)
- Decrement frequency of 'n':
frequencyDifference.put('n', -1)
frequencyDifference
= {'g': 0, 'd': 0, 'a': 1, 'e': -1, 'r': 1, 's': -1, 'u': 1, 'i': -1, 'm': 1, 'n': -1}
- i = 6:
charT = 'e'
,charS = 'g'
- Increment frequency of 'e':
frequencyDifference.put('e', 0)
- Decrement frequency of 'g':
frequencyDifference.put('g', -1)
frequencyDifference
= {'g': -1, 'd': 0, 'a': 1, 'e': 0, 'r': 1, 's': -1, 'u': 1, 'i': -1, 'm': 1, 'n': -1}
- i = 7:
charT = 's'
,charS = 'u'
- Increment frequency of 's':
frequencyDifference.put('s', 0)
- Decrement frequency of 'u':
frequencyDifference.put('u', 0)
frequencyDifference
= {'g': -1, 'd': 0, 'a': 1, 'e': 0, 'r': 1, 's': 0, 'u': 0, 'i': -1, 'm': 1, 'n': -1}
- i = 8:
charT = 'p'
,charS = 'r'
- Increment frequency of 'p':
frequencyDifference.put('p', 1)
- Decrement frequency of 'r':
frequencyDifference.put('r', 0)
frequencyDifference
= {'g': -1, 'd': 0, 'a': 1, 'e': 0, 'r': 0, 's': 0, 'u': 0, 'i': -1, 'm': 1, 'n': -1, 'p': 1}
- i = 9:
charT = 'g'
,charS = 'u'
- Increment frequency of 'g':
frequencyDifference.put('g', 0)
- Decrement frequency of 'u':
frequencyDifference.put('u', -1)
frequencyDifference
= {'g': 0, 'd': 0, 'a': 1, 'e': 0, 'r': 0, 's': 0, 'u': -1, 'i': -1, 'm': 1, 'n': -1, 'p': 1}
- i = 10:
charT = 'n'
,charS = 's'
- Increment frequency of 'n':
frequencyDifference.put('n', 0)
- Decrement frequency of 's':
frequencyDifference.put('s', -1)
frequencyDifference
= {'g': 0, 'd': 0, 'a': 1, 'e': 0, 'r': 0, 's': -1, 'u': -1, 'i': -1, 'm': 1, 'n': 0, 'p': 1}
- i = 0:
-
Calculate steps:
- Initialize
steps
= 0 - Iterate over
frequencyDifference
values:- 'g' = 0 -> steps += 0
- 'd' = 0 -> steps += 0
- 'a' = 1 -> steps += 1
- 'e' = 0 -> steps += 0
- 'r' = 0 -> steps += 0
- 's' = -1 -> steps += 0
- 'u' = -1 -> steps += 0
- 'i' = -1 -> steps += 0
- 'm' = 1 -> steps += 1
- 'n' = 0 -> steps += 0
- 'p' = 1 -> steps += 1
- Initialize
-
Return result:
steps
= 3
Thus, the minimum number of replacements needed to make "garumdespgn" an anagram of "designgurus" is 3.
Code
Complexity Analysis
Time Complexity
- The code performs a single loop over the length of the strings
s
andt
, which is O(n), wheren
is the length of the strings. - The
HashMap
operations (put and get) are average O(1). - Therefore, the overall time complexity is O(n).
Space Complexity
- The space complexity is determined by the
HashMap
, which stores at most 26 character frequencies, resulting in O(1) space complexity since the number of unique characters is constant.
.....
.....
.....
Table of Contents
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible
Contents are not accessible