Devin's Blog

Minimum Number Of Steps To Make Two Strings Anagram

2 min read

Intuition

  • The main insight here is: the concept of excess vs. deficit.
  • Important constraints:
    • s and t are of the same length
    • You change characters in t
  • You have an excess whenever there are too many characters in t.
  • This either means:
    • A character in t exists in s, but it exists too many times
    • A character in t does not exist in s
  • Those are the characters that need to be replaced
  • Note that if you have an excess of characters in t, this is equivalent to s having a deficit of characters to match t with.
    • Put another way, by replacing each excess character with a character from s, you are handling the deficit.

Complexity

Runtime

, where N is max. of the length of S and T.

  • That is the worst case, but on average we get since lookup on a dictionary is (no collisions).

Space

Code

One Liner

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        return (Counter(s) - Counter(t)).total()
  • .total() returns the difference in the number of characters.
  • This amounts to “the count of the number of characters in s that are not in t”

Deficit

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        t_counter = Counter(t)
        s_counter = Counter(s)
 
        deficit = 0
        for c in s_counter:
            if c in t:
                if t_counter[c] < s_counter[c]:
                    deficit += s_counter[c] - t_counter[c]
            else:
                deficit += s_counter[c]
        
        return deficit
  • Note that it makes more sense with the excess version, since you are replacing characters in t, so you should replace the excess characters in t.

Excess

class Solution:
    def minSteps(self, s: str, t: str) -> int:
        t_counter = Counter(t)
        s_counter = Counter(s)
 
        excess = 0
        for c in t_counter:
            if c in s:
                if t_counter[c] > s_counter[c]:
                    excess += t_counter[c] - s_counter[c]
            else:
                excess += t_counter[c]
        
        return excess

Notes

Cards

START Basic Front: Minimum Number Of Steps To Make Two Strings Anagram Back: Count the number of characters in s that are not in t

END

References

Graph View