Skip to content

3889. Mirror Frequency Distance

Description

You are given a string s consisting of lowercase English letters and digits.

For each character, its mirror character is defined by reversing the order of its character set:

  • For letters, the mirror of a character is the letter at the same position from the end of the alphabet.
    • For example, the mirror of 'a' is 'z', and the mirror of 'b' is 'y', and so on.
  • For digits, the mirror of a character is the digit at the same position from the end of the range '0' to '9'.
    • For example, the mirror of '0' is '9', and the mirror of '1' is '8', and so on.

For each unique character c in the string:

  • Let m be its mirror character.
  • Let freq(x) denote the number of times character x appears in the string.
  • Compute the absolute difference between their frequencies, defined as: |freq(c) - freq(m)|

The mirror pairs (c, m) and (m, c) are the same and must be counted only once.

Return an integer denoting the total sum of these values over all such distinct mirror pairs.

Β 

Example 1:

Input: s = "ab1z9"

Output: 3

Explanation:

For every mirror pair:

c m freq(c) freq(m) |freq(c) - freq(m)|
a z 1 1 0
b y 1 0 1
1 8 1 0 1
9 0 1 0 1

Thus, the answer is 0 + 1 + 1 + 1 = 3.

Example 2:

Input: s = "4m7n"

Output: 2

Explanation:

c m freq(c) freq(m) |freq(c) - freq(m)|
4 5 1 0 1
m n 1 1 0
7 2 1 0 1

Thus, the answer is 1 + 0 + 1 = 2.​​​​​​​

Example 3:

Input: s = "byby"

Output: 0

Explanation:

c m freq(c) freq(m) |freq(c) - freq(m)|
b y 2 2 0

Thus, the answer is 0.

Β 

Constraints:

  • 1 <= s.length <= 5 * 105
  • s consists only of lowercase English letters and digits.

Solutions

Solution 1: Hash Table

We first use a hash table \(\textit{freq}\) to count the frequency of each character in string \(s\).

Then, we iterate over each key-value pair \((c, v)\) in \(\textit{freq}\), where \(c\) is the character and \(v\) is the number of times character \(c\) appears in string \(s\). For each character \(c\), we compute its mirror character \(m\) and calculate \(|freq(c) - freq(m)|\). To avoid counting mirror pairs twice, we use a hash set \(\textit{vis}\) to track already-visited characters.

Finally, we return the sum of absolute differences over all distinct mirror pairs.

The time complexity is \(O(n)\), where \(n\) is the length of string \(s\). The space complexity is \(O(|\Sigma|)\), where \(\Sigma\) is the set of distinct characters in string \(s\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def mirrorFrequency(self, s: str) -> int:
        freq = Counter(s)
        ans = 0
        vis = set()
        for c, v in freq.items():
            m = (
                chr(ord("a") + 25 - (ord(c) - ord("a")))
                if c.isalpha()
                else str(9 - int(c))
            )
            if m in vis:
                continue
            vis.add(c)
            ans += abs(v - freq[m])
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public int mirrorFrequency(String s) {
        Map<Character, Integer> freq = new HashMap<>();
        for (char c : s.toCharArray()) {
            freq.merge(c, 1, Integer::sum);
        }

        int ans = 0;
        Set<Character> vis = new HashSet<>();

        for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
            char c = entry.getKey();
            int v = entry.getValue();

            char m;
            if (Character.isLetter(c)) {
                m = (char) ('a' + 25 - (c - 'a'));
            } else {
                m = (char) ('0' + (9 - (c - '0')));
            }

            if (vis.contains(m)) {
                continue;
            }
            vis.add(c);

            int mv = freq.getOrDefault(m, 0);
            ans += Math.abs(v - mv);
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int mirrorFrequency(string s) {
        unordered_map<char, int> freq;
        for (char c : s) {
            freq[c]++;
        }

        int ans = 0;
        unordered_set<char> vis;

        for (auto& [c, v] : freq) {
            char m;
            if (isalpha(c)) {
                m = 'a' + 25 - (c - 'a');
            } else {
                m = '0' + (9 - (c - '0'));
            }

            if (vis.count(m)) {
                continue;
            }
            vis.insert(c);

            int mv = freq.count(m) ? freq[m] : 0;
            ans += abs(v - mv);
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func mirrorFrequency(s string) int {
    freq := make(map[rune]int)
    for _, c := range s {
        freq[c]++
    }

    ans := 0
    vis := make(map[rune]bool)

    for c, v := range freq {
        var m rune
        if c >= 'a' && c <= 'z' {
            m = 'a' + 25 - (c - 'a')
        } else {
            m = '0' + (9 - (c - '0'))
        }

        if vis[m] {
            continue
        }
        vis[c] = true

        mv := freq[m]
        ans += abs(v - mv)
    }

    return ans
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function mirrorFrequency(s: string): number {
    const freq = new Map<string, number>();
    for (const c of s) {
        freq.set(c, (freq.get(c) || 0) + 1);
    }

    let ans = 0;
    const vis = new Set<string>();

    for (const [c, v] of freq.entries()) {
        let m: string;

        if (/[a-z]/.test(c)) {
            m = String.fromCharCode('a'.charCodeAt(0) + 25 - (c.charCodeAt(0) - 'a'.charCodeAt(0)));
        } else {
            m = String(9 - Number(c));
        }

        if (vis.has(m)) {
            continue;
        }
        vis.add(c);

        const mv = freq.get(m) || 0;
        ans += Math.abs(v - mv);
    }

    return ans;
}

Comments