What is the time complexity of LeetCode 1347. Minimum Number of Steps to Make Two Strings Anagram?

The Python solution on this page runs in O(m + n).

What is the space complexity of LeetCode 1347. Minimum Number of Steps to Make Two Strings Anagram?

The Python solution on this page uses O(|\Sigma|), where m and n are the lengths of the strings \textit{s} and \textit{t}, respectively, and |\Sigma| is the size of the character set auxiliary space.

Minimum Number of Steps to Make Two Strings Anagram — LeetCode 1347 Python Solution

MediumHash TableStringCounting

Problem: #1347
Pattern: Hash Map
Reading time: 2 min
Source: leetcode.com

The problem

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.

Example

Input: s = "bab", t = "aba"
Output: 1
Explanation: Replace the first 'a' in t with b, t = "bba" which is anagram of s.

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(m + n)
Space	O(\|\Sigma\|), where m and n are the lengths of the strings \textit{s} and \textit{t}, respectively, and \|\Sigma\| is the size of the character set auxiliary

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1347. Minimum Number of Steps to Make Two Strings Anagram is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table and Counting.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1347. Minimum Number of Steps to Make Two Strings Anagram?: LeetCode 1347. Minimum Number of Steps to Make Two Strings Anagram is rated Medium on LeetCode.
What is the time complexity of LeetCode 1347. Minimum Number of Steps to Make Two Strings Anagram?: The Python solution on this page runs in O(m + n).
What is the space complexity of LeetCode 1347. Minimum Number of Steps to Make Two Strings Anagram?: The Python solution on this page uses O(|\Sigma|), where m and n are the lengths of the strings \textit{s} and \textit{t}, respectively, and |\Sigma| is the size of the character set auxiliary space.
What topics does LeetCode 1347. Minimum Number of Steps to Make Two Strings Anagram cover?: LeetCode 1347. Minimum Number of Steps to Make Two Strings Anagram is tagged Hash Table, String and Counting on LeetCode.