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 仅由小写英文字母和数字组成。

解法

方法一：哈希表

思考

字母与数字各自关于字符表镜像，对每个无序镜像对累加频次绝对差。一次计数即可。

同一对 \((c,m)\) 与 \((m,c)\) 只算一次，需标记已访问。

先统计频次，再对每个未访问字符求镜像并累加 \(|freq(c)-freq(m)|\)，同时标记 \(c\)。

镜像不在串中时频次视为 \(0\)。

先用哈希表 \(\textit{freq}\) 统计字符串 \(s\) 中每个字符的出现次数。

再遍历 \(\textit{freq}\) 中的每个键值对 \((c, v)\)，其中 \(c\) 是字符，\(v\) 是它出现的次数。对每个字符 \(c\)，算出镜像字符 \(m\)，并计算 \(|freq(c) - freq(m)|\)。为避免同一镜像对被算两次，用哈希集合 \(\textit{vis}\) 记录已经访问过的字符。

最后返回所有不同镜像对的绝对差之和。

时间复杂度 \(O(n)\)，其中 \(n\) 是字符串 \(s\) 的长度。空间复杂度 \(O(|\Sigma|)\)，其中 \(\Sigma\) 是 \(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. 镜像频次距离

题目描述

解法

方法一：哈希表

评论