3889. 镜像频次距离

题目描述

给你一个由小写英文字母和数字组成的字符串 s。

对于每个字符，其 镜像字符 根据逆序定义其字符集合：

对于字母，某字符的镜像字符是字母表中从末尾与其位置相同的字母。
- 例如，'a' 的镜像字符是 'z'，'b' 的镜像字符是 'y'，以此类推。
对于数字，某字符的镜像字符是范围 '0' 到 '9' 中从末尾与其位置相同的数字。
- 例如，'0' 的镜像字符是 '9'，'1' 的镜像字符是 '8'，以此类推。

对于字符串中每个唯一字符 c：

设 m 为其 镜像字符 。
设 freq(x) 表示字符 x 在字符串中出现的次数。
计算其与镜像字符出现次数之间的 绝对差，定义为：|freq(c) - freq(m)|

镜像对 (c, m) 和 (m, c) 被视为相同，只能被计算一次。

返回一个整数，表示所有这些 不同的镜像对 的绝对差之和。

示例 1：

输入： s = "ab1z9"

输出： 3

解释：

对于每个镜像对：

`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

因此，答案是 0 + 1 + 1 + 1 = 3。

示例 2：

输入： s = "4m7n"

输出： 2

解释：

`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

因此，答案是 1 + 0 + 1 = 2。

示例 3：

输入：s = "byby"

输出：0

解释：

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

因此，答案是 0 。

提示:

1 <= s.length <= 5 * 10⁵
s 仅由小写英文字母和数字组成。

解法

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\).

Python3JavaC++GoTypeScript

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

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;
    }
}

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;
    }
};

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
}

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;
}

3889. 镜像频次距离

题目描述

解法

Solution 1: Hash Table

评论