Problem Explanation

In this problem, we are given two strings s and t of equal lengths. We can choose any character from the string t and replace it with another character. The task is to convert the string t into an anagram of s with minimum steps.

An anagram of a string is another string that contains the same characters, only the order of characters can be different.

Let's illustrate this on Example 1:

s = "bab" t = "aba"

In the initial state, t is not an anagram of s. The s string contains two 'b' characters, but t contains only one. Therefore, we can take the first 'a' in t and replace it with 'b', to make t = "bba". Now, t is an anagram of s. The number of steps required in this case is 1.

Solution Walk-through

To solve this problem efficiently, we can utilize a counting technique.

First, we create a count list of size 26 to hold the character counts of string s.

Then, we iterate over the characters in s, incrementing the corresponding index in the count array. This effectively counts the characters in s.

Next, we iterate over the characters in t, decrementing the corresponding index in the count array. This essentially subtracts the counts of characters found in t.

Finally, we find the sum of absolute values in the count array and divide it by two. This gives us the minimum number of steps required to make t an anagram of s.

Python

1
2python
3class Solution:
4    def minSteps(self, s: str, t:str) -> int:
5        count = [0]*26
6
7        for c in s:
8            count[ord(c)-ord('a')] += 1
9
10        for c in t:
11            count[ord(c)-ord('a')] -= 1
12
13        return sum(abs(i) for i in count) // 2

Java

1
2java
3class Solution {
4    public int minSteps(String s, String t) {
5        int[] count = new int[26];
6        
7        for(char c : s.toCharArray())
8            count[c - 'a']++;
9        
10        for(char c : t.toCharArray())
11            count[c - 'a']--;
12        
13        int steps = 0;
14        for(int i : count)
15            steps += Math.abs(i);
16        
17        return steps / 2;
18    }
19}

JavaScript

1
2javascript
3class Solution {
4    minSteps(s, t) {
5        let count = new Array(26).fill(0);
6
7        for(let c of s)
8            count[c.charCodeAt() - 'a'.charCodeAt()]++;
9
10        for(let c of t)
11            count[c.charCodeAt() - 'a'.charCodeAt()]--;
12
13        return count.reduce((sum, value) => sum + Math.abs(value), 0) / 2;
14    }
15}

C++

1
2cpp
3class Solution {
4public:
5    int minSteps(string s, string t) {
6        vector<int> count(26);
7
8        for (const char c : s)
9            ++count[c - 'a'];
10
11        for (const char c : t)
12            --count[c - 'a'];
13
14        return accumulate(count.begin(), count.end(), 0, [](int a, int b) { return a + abs(b); }) / 2;
15    }
16};

C#

1
2csharp
3public class Solution {
4    public int MinSteps(string s, string t) {
5        int[] count = new int[26];
6
7        foreach(char c in s)
8            count[c - 'a']++;
9
10        foreach(char c in t)
11            count[c - 'a']--;
12
13        return count.Sum(Math.Abs) / 2;
14    }
15}

The solutions in each language rely on the same overall approach: using a count array to track the characters in s and t, and then finding the total changes needed to make t an anagram of s.This approach works because it simplifies the process of matching each character between the two strings. Rather than trying to directly modify t to match s, we're looking at the differences between the two strings in terms of their character counts. The operations on the count array give us a way to quantify those differences.

The reason we divide the final sum by 2 is that each mismatched character contributes twice to the sum; once when we increment for s and once when we decrement for t.

For instance, if one character 'z' is present in s but not in t, count[ord('z')-ord('a')] is incremented once. When 'z' is not found in t, count[ord('z')-ord('a')] is not decremented, resulting in a discrepancy of 1 after both strings have been traversed. So we divide the final sum by 2 to get the right number of steps.

In conclusion, the aforementioned approach provides an effective way to determine the minimum number of steps to make one string an anagram of another. It offers good time efficiency because both strings are traversed only once (linear time complexity), and it doesn't require any additional data structures, keeping space complexity to a minimum as well.