Сложность: medium
Даны две строки одинаковой длины 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.
👨💻 Алгоритм:
1⃣Вычислить разницу частот символов в строках t и s, сохраняя результаты в массиве count.
2⃣Подсчитать количество символов, которые нужно заменить в t, добавляя в ans только положительные значения из массива count.
3⃣Вернуть ans как минимальное количество шагов для превращения t в анаграмму строки s.
😎 Решение:
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
Ставь 👍 и забирай 📚 Базу знаний