[leetcode, medium] Minimum Number of Steps to Make Two Strings Anagram

Given two equal-size strings 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.

Example 4:

Input: s = "xxyyzz", t = "xxyyzz" Output: 0

Example 5:

Input: s = "friend", t = "family" Output: 4

 

Constraints:

• 1 <= s.length <= 50000
• s.length == t.length
• s and t contain lower-case English letters only.

anagram이란 두개의 문자열이 있을때 두 문자열내에 있는 문자의 조합의 개수가 일치하는것을 말한다.

예를들어, aba와 aab는 서로 순서는 다르지만 a가 2개 b가1개 있는 문자의 조합의 개수는 일치하기 때문에 anagram이다.

 

문제는 두 문자열이 주어졌을때 둘중 하나의 문자열 내의 몇개의 문자를 고쳐야 두 문자열이 서로 anagram이 될 수 있는지를 묻는 문제이다.

 

1. 우선 알파벳 소문자의 개수는 26개 이므로 26사이즈 짜리 배열 2개를 선언한다.

2. 그리고 나서 s와 t의 문자열의 길이가 똑같으므로 s와 t를 순회하면서 배열에 두 문자열의 문자를 코드로 바꿔 배열 2개에 저장한다.

3. 그러면 각 문자열의 문자들이 총 몇번씩 등장하는지를 셀 수 있게 된다.

4. 그 두 배열을 가지고 한쪽에서 겹치는 문자의 개수를 제거해주고 남은 개수를 세면 그게 정답이다.

5. 이게 가능한 이유는 겹치지 않는 문자가 남았다는것은 다른 문자열의 문자로 그냥 교체하면 된다는 의미이기 때문이다.

/**
 * @param {string} s
 * @param {string} t
 * @return {number}
 */
var minSteps = function(s, t) {
    const arr1 = Array(26).fill(0);
    const arr2 = Array(26).fill(0);
    for(let i=0; i<s.length; i++) {
        const c1 = s[i].charCodeAt() - 97;
        const c2 = t[i].charCodeAt() - 97;
        
        arr1[c1]++;
        arr2[c2]++;
    }
    let result = 0;
    for(let i=0; i<26; i++) {
        if(arr1[i] < arr2[i]) result += arr2[i] - arr1[i];
    }
    
    return result;
};