3889. Mirror Frequency Text

Problem Statement in English

You’re given a string s consisting of lowercase English letters and digits. You have to find the minimum number of characters that need to be removed from s such that the frequency of each character in the resulting string is equal to the frequency of its mirror character.

For example the mirror character of a is z, the mirror character of b is y, and so on. The mirror character of 0 is 9, the mirror character of 1 is 8, and so on.

Return the minimum number of characters that need to be removed from s.

Approach

We can just pre compute the mirror characters and then calculate the frequency of each character in the string. Then we can just iterate through the frequency map and calculate the result.

And we’re done!

Solution in Python

class Solution:
    def mirrorFrequency(self, s: str) -> int:
        hm = Counter(s)

        mirror = {}

        l, r = "a", "z"

        while l < r:
            mirror[l] = r
            mirror[r] = l

            l = chr(ord(l) + 1)
            r = chr(ord(r) - 1)

        l, r = 0, 9

        while l < r:
            mirror[str(l)] = str(r)
            mirror[str(r)] = str(l)

            l += 1
            r -= 1

        res = 0
        seen = set()

        for k in hm:
            if k in seen or mirror[k] in seen:
                continue
            seen.add(k)
            seen.add(mirror[k])

            res += abs(hm[k] - hm[mirror[k]])

        return res        

Complexity

• Time: $O(n)$
  Since we traverse the string once to calculate the frequency and then we traverse the frequency map once to calculate the result.

• Space: $O(n)$
  Since we store the frequency of each character in a dictionary.

And we are done.