2186.md

2186. Minimum Number of Steps to Make Two Strings Anagram II

Level:

Topic:

Similar Problem:

• 1347. Minimum Number of Steps to Make Two Strings Anagram

Question

You are given two strings s and t. In one step, you can append any character to either s or t.

Input: s = "leetcode", t = "coats"
Output: 7
Explanation:

• In 2 steps, we can append the letters in "as" onto s = "leetcode", forming s = "leetcodeas".
• In 5 steps, we can append the letters in "leede" onto t = "coats", forming t = "coatsleede". "leetcodeas" and "coatsleede" are now anagrams of each other.
  We used a total of 2 + 5 = 7 steps.
  It can be shown that there is no way to make them anagrams of each other with less than 7 steps.

Intuition

The goal of this problem is to find out the difference in charcters in s and t and the answer is the length difference and their character difference in total.

1. Check the difference betwen s and t = the extra characters needed in s
2. To get the extra characters needed in t, use s.lenght()+diff - t.length()

Code

Time: O(n+m)
Space: O(26) = O(1)

public int minSteps(String s, String t) {
    int [] freq = new int[26];
    int diff = 0;

    for (char c: s.toCharArray())
        freq[c-'a']++;

    for (char c: t.toCharArray()) {
        freq[c-'a']--;
        if (freq[c-'a'] < 0)
            diff++;
    }

    return s.length() - t.length() + (diff * 2);
}