1347. Minimum Number of Steps to Make Two Strings Anagram

leetcode medium

#array#csharp#leetcode#math#medium#string

Task

Даны две строки одинаковой длины s и t. За один шаг вы можете выбрать любой символ строки t и заменить его другим символом.

Вернуть минимальное количество шагов, чтобы сделать t анаграммой строки s.

Анаграмма строки — это строка, которая содержит те же символы в другом (или том же) порядке.

Пример:

Input: s = "bab", t = "aba"

Output: 1

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

C# solution

matched/original

public class Solution {
    public int MinSteps(string s, string t) {
        int[] count = new int[26];
        
        for (int i = 0; i < s.Length; i++) {
            count[t[i] - 'a']++;
            count[s[i] - 'a']--;
        }
        int ans = 0;
        for (int i = 0; i < 26; i++) {
            ans += Math.Max(0, count[i]);
        }
        return ans;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinSteps(string s, string t) {
        vector<int>& count = new int[26];
        
        for (int i = 0; i < s.size(); i++) {
            count[t[i] - 'a']++;
            count[s[i] - 'a']--;
        }
        int ans = 0;
        for (int i = 0; i < 26; i++) {
            ans += max(0, count[i]);
        }
        return ans;
    }
}

Java solution

matched/original

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

        int ans = 0;
        for (int i = 0; i < 26; i++) {
            ans += Math.max(0, count[i]);
        }

        return ans;
    }
}

Python solution

matched/original

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        count = [0] * 26
        
        for i in range(len(s)):
            count[ord(t[i]) - ord('a')] += 1
            count[ord(s[i]) - ord('a')] -= 1

        ans = 0
        for i in range(26):
            ans += max(0, count[i])

        return ans

Explanation

Algorithm

Вычислить разницу частот символов в строках t и s, сохраняя результаты в массиве count.

Подсчитать количество символов, которые нужно заменить в t, добавляя в ans только положительные значения из массива count.

Вернуть ans как минимальное количество шагов для превращения t в анаграмму строки s.

😎