Medium

题目描述

给你一个由小写英文字母和数字组成的字符串 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
解释：
对于每个镜像对：
- a 和 z：freq(a)=1, freq(z)=1，|1-1|=0
- b 和 y：freq(b)=1, freq(y)=0，|1-0|=1
- 1 和 8：freq(1)=1, freq(8)=0，|1-0|=1
- 9 和 0：freq(9)=1, freq(0)=0，|1-0|=1

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

示例 2：

输入：s = "4m7n"
输出：2

示例 3：

输入：s = "byby"
输出：0

约束条件：

  • 1 <= s.length <= 5 * 10^5
  • s 只包含小写英文字母和数字。

解题思路

这道题的核心思路是理解镜像字符的定义，并统计每对镜像字符频率差的绝对值。

解题步骤：

  1. 定义镜像关系：

    • 对于字母：‘a’↔‘z’, ‘b’↔‘y’, …, 通用公式为 (char - 'a') + ('z' - char) = 'z' - 'a'
    • 对于数字：‘0’↔‘9’, ‘1’↔‘8’, …, 通用公式为 (char - '0') + ('9' - char) = '9' - '0'

  2. 统计字符频率：遍历字符串，用哈希表记录每个字符的出现次数。

  3. 计算镜像对差值：

    • 遍历所有可能的字符（‘a’-‘z’ 和 ‘0’-‘9’）
    • 对每个字符找到其镜像字符
    • 为避免重复计算，只处理字典序较小的字符或使用其他去重策略
    • 计算 |freq(c) - freq(mirror)| 并累加

  4. 优化策略：

    • 可以只遍历字符串中实际出现的字符
    • 使用集合记录已处理的镜像对避免重复

时间复杂度：O(n)，其中 n 是字符串长度 空间复杂度：O(1)，哈希表最多存储 36 个字符（26个字母 + 10个数字）

代码实现

class Solution {
public:
    int mirrorFrequency(string s) {
        unordered_map<char, int> freq;
        for (char c : s) {
            freq[c]++;
        }
        
        int result = 0;
        set<pair<char, char>> processed;
        
        for (auto& [c, count] : freq) {
            char mirror;
            if (c >= 'a' && c <= 'z') {
                mirror = 'z' - (c - 'a');
            } else {
                mirror = '9' - (c - '0');
            }
            
            pair<char, char> p = {min(c, mirror), max(c, mirror)};
            if (processed.find(p) == processed.end()) {
                processed.insert(p);
                result += abs(freq[c] - freq[mirror]);
            }
        }
        
        return result;
    }
};

class Solution:
    def mirrorFrequency(self, s: str) -> int:
        from collections import Counter
        
        freq = Counter(s)
        result = 0
        processed = set()
        
        for c in freq:
            if c.isalpha():
                mirror = chr(ord('z') - (ord(c) - ord('a')))
            else:
                mirror = chr(ord('9') - (ord(c) - ord('0')))
            
            pair = tuple(sorted([c, mirror]))
            if pair not in processed:
                processed.add(pair)
                result += abs(freq[c] - freq.get(mirror, 0))
        
        return result

public class Solution {
    public int MirrorFrequency(string s) {
        var freq = new Dictionary<char, int>();
        foreach (char c in s) {
            freq[c] = freq.GetValueOrDefault(c, 0) + 1;
        }
        
        int result = 0;
        var processed = new HashSet<string>();
        
        foreach (var kvp in freq) {
            char c = kvp.Key;
            char mirror;
            
            if (c >= 'a' && c <= 'z') {
                mirror = (char)('z' - (c - 'a'));
            } else {
                mirror = (char)('9' - (c - '0'));
            }
            
            string pair = c < mirror ? $"{c}{mirror}" : $"{mirror}{c}";
            if (!processed.Contains(pair)) {
                processed.Add(pair);
                int mirrorFreq = freq.GetValueOrDefault(mirror, 0);
                result += Math.Abs(freq[c] - mirrorFreq);
            }
        }
        
        return result;
    }
}

var mirrorFrequency = function(s) {
    const freq = {};
    for (let c of s) {
        freq[c] = (freq[c] || 0) + 1;
    }
    
    let result = 0;
    const processed = new Set();
    
    for (let c in freq) {
        let mirror;
        if (c >= 'a' && c <= 'z') {
            mirror = String.fromCharCode('z'.charCodeAt(0) - (c.charCodeAt(0) - 'a'.charCodeAt(0)));
        } else {
            mirror = String.fromCharCode('9'.charCodeAt(0) - (c.charCodeAt(0) - '0'.charCodeAt(0)));
        }
        
        const pair = c < mirror ? c + mirror : mirror + c;
        if (!processed.has(pair)) {
            processed.add(pair);
            result += Math.abs(freq[c] - (freq[mirror] || 0));
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大O表示法说明
时间复杂度O(n)需要遍历字符串统计频率，然后遍历哈希表计算结果，n为字符串长度
空间复杂度O(1)哈希表最多存储36个字符（26个字母+10个数字），为常数空间