1347-kir3i.md

1347. Minimum Number of Steps to Make Two Strings Anagram

Solution

• 시간복잡도: O(N)

• 알고리즘

  문자열, 구현

• 풀이설명

  기존 문자 s에 있는 알파벳과 새로운 문자 t에 있는 알파벳을 비교하여 대체할 수 없는 알파벳의 수를 찾아내면 됩니다. 기존 문자 s에 포함된 알파벳의 수를 cnt에 저장해두고 t를 읽으면서 cnt를 참고하여 부족한 알파벳의 수를 찾아냅니다.

• 소스코드

  • C++

    class Solution {
    public:
        int cnt[26];
        int ans;
        int minSteps(string s, string t) {
            for(const char &c: s)
                cnt[c-'a']++;
            for(const char &c: t)
                if(cnt[c-'a']-- <= 0)
                    ans++;
            return ans;
        }
    };

  • Python

    class Solution:
        def minSteps(self, s, t):
            cnt = {}
            for c in s:
                if c not in cnt:
                    cnt[c] = 1
                else:
                    cnt[c] += 1
            ans = 0
            for c in t:
                if c in cnt and cnt[c] > 0:
                    cnt[c] -= 1
                else:
                    ans += 1
                
            return ans

  • Java

    class Solution {
        public int[] cnt = new int[26];
        public int ans = 0;
        public int minSteps(String s, String t) {
            for(int i=0; i<s.length(); i++)
                cnt[s.charAt(i)-'a']++;
            for(int i=0; i<t.length(); i++)
                if(cnt[t.charAt(i)-'a']-- <= 0)
                    ans++;
            return ans;
        }
    }