LeetCode 1347. Minimum Number of Steps to Make Two Strings Anagram Solution in Java, C++, Python & More | Explanation + Code

Description

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 * 104
• s.length == t.length
• s and t consist of lowercase English letters only.

Solutions

Solution 1: Counting

We can use a hash table or an array cnt to count the occurrences of each character in the string s. Then, we traverse the string t. For each character, we decrement its count in cnt. If the decremented value is less than 0, it means that this character appears more times in the string t than in the string s. In this case, we need to replace this character and increment the answer by one.

After the traversal, we return the answer.

The time complexity is O(m + n), and the space complexity is O(|Σ|), where m and n are the lengths of the strings s and t, respectively, and |Σ| is the size of the character set. In this problem, the character set consists of lowercase letters, so |Σ| = 26.

PythonJavaC++GoTypeScriptJavaScript

class Solution: def minSteps(self, s: str, t: str) -> int: cnt = Counter(s) ans = 0 for c in t: cnt[c] -= 1 ans += cnt[c] < 0 return ans(code-box)

class Solution { public int minSteps(String s, String t) { int[] cnt = new int[26]; for (char c : s.toCharArray()) { cnt[c - 'a']++; } int ans = 0; for (char c : t.toCharArray()) { if (--cnt[c - 'a'] < 0) { ans++; } } return ans; } }(code-box)

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) { if (--cnt[c - 'a'] < 0) { ++ans; } } return ans; } };(code-box)

func minSteps(s string, t string) (ans int) { cnt := [26]int{} for _, c := range s { cnt[c-'a']++ } for _, c := range t { cnt[c-'a']-- if cnt[c-'a'] < 0 { ans++ } } return }(code-box)

function minSteps(s: string, t: string): number { const cnt: number[] = Array(26).fill(0); for (const c of s) { ++cnt[c.charCodeAt(0) - 97]; } let ans = 0; for (const c of t) { if (--cnt[c.charCodeAt(0) - 97] < 0) { ++ans; } } return ans; }(code-box)

/** * @param {string} s * @param {string} t * @return {number} */ var minSteps = function (s, t) { const cnt = Array(26).fill(0); for (const c of s) { ++cnt[c.charCodeAt(0) - 97]; } let ans = 0; for (const c of t) { if (--cnt[c.charCodeAt(0) - 97] < 0) { ++ans; } } return ans; };(code-box)