字符串字符分组排序

问题

将字符串 "abacba" 转换成 "aaa,bb,c"，即相同字符分组，按出现次数降序排列，用逗号分隔。

答案

这道题考察字符串处理、哈希表统计和排序。核心步骤：

1. 统计每个字符出现次数
2. 按次数降序排序
3. 生成分组字符串
4. 用逗号连接

---

基础实现

function groupAndSort(str: string): string {
  // 1. 统计字符频次
  const countMap = new Map<string, number>();

  for (const char of str) {
    countMap.set(char, (countMap.get(char) || 0) + 1);
  }

  // 2. 转换为数组并按频次降序排序
  const sorted = Array.from(countMap.entries())
    .sort((a, b) => b[1] - a[1]);

  // 3. 生成分组字符串
  const groups = sorted.map(([char, count]) => char.repeat(count));

  // 4. 用逗号连接
  return groups.join(',');
}

// 测试
console.log(groupAndSort('abacba')); // 'aaa,bb,c'
console.log(groupAndSort('hello'));  // 'll,ee,h,o' 或 'll,h,e,o'（取决于排序稳定性）

---

使用对象统计

function groupAndSortV2(str: string): string {
  // 使用对象统计
  const counts: Record<string, number> = {};

  for (const char of str) {
    counts[char] = (counts[char] || 0) + 1;
  }

  // 排序并生成结果
  return Object.entries(counts)
    .sort((a, b) => b[1] - a[1])
    .map(([char, count]) => char.repeat(count))
    .join(',');
}

---

一行代码实现

const groupAndSortOneLiner = (str: string): string =>
  Object.entries(
    [...str].reduce<Record<string, number>>(
      (acc, char) => ({ ...acc, [char]: (acc[char] || 0) + 1 }),
      {}
    )
  )
    .sort((a, b) => b[1] - a[1])
    .map(([c, n]) => c.repeat(n))
    .join(',');

---

处理排序稳定性

当频次相同时，可以按字符顺序排序：

function groupAndSortStable(str: string): string {
  const countMap = new Map<string, number>();

  for (const char of str) {
    countMap.set(char, (countMap.get(char) || 0) + 1);
  }

  return Array.from(countMap.entries())
    .sort((a, b) => {
      // 先按频次降序
      if (b[1] !== a[1]) return b[1] - a[1];
      // 频次相同按字符升序
      return a[0].localeCompare(b[0]);
    })
    .map(([char, count]) => char.repeat(count))
    .join(',');
}

// 测试
console.log(groupAndSortStable('hello')); // 'll,e,h,o'（e < h < o）

---

保持原字符首次出现顺序

function groupAndSortByFirstAppearance(str: string): string {
  const countMap = new Map<string, number>();
  const orderMap = new Map<string, number>(); // 记录首次出现位置

  for (let i = 0; i < str.length; i++) {
    const char = str[i];
    countMap.set(char, (countMap.get(char) || 0) + 1);

    if (!orderMap.has(char)) {
      orderMap.set(char, i);
    }
  }

  return Array.from(countMap.entries())
    .sort((a, b) => {
      // 先按频次降序
      if (b[1] !== a[1]) return b[1] - a[1];
      // 频次相同按首次出现顺序
      return orderMap.get(a[0])! - orderMap.get(b[0])!;
    })
    .map(([char, count]) => char.repeat(count))
    .join(',');
}

---

扩展：支持自定义分隔符和排序

interface GroupOptions {
  separator?: string;          // 分隔符
  order?: 'asc' | 'desc';      // 排序顺序
  sortBy?: 'count' | 'char';   // 排序依据
  caseSensitive?: boolean;     // 大小写敏感
}

function groupCharacters(str: string, options: GroupOptions = {}): string {
  const {
    separator = ',',
    order = 'desc',
    sortBy = 'count',
    caseSensitive = true
  } = options;

  // 统计
  const countMap = new Map<string, number>();
  const processedStr = caseSensitive ? str : str.toLowerCase();

  for (const char of processedStr) {
    countMap.set(char, (countMap.get(char) || 0) + 1);
  }

  // 排序
  const entries = Array.from(countMap.entries());

  entries.sort((a, b) => {
    let compare: number;

    if (sortBy === 'count') {
      compare = a[1] - b[1];
    } else {
      compare = a[0].localeCompare(b[0]);
    }

    return order === 'desc' ? -compare : compare;
  });

  // 生成结果
  return entries
    .map(([char, count]) => char.repeat(count))
    .join(separator);
}

// 测试
console.log(groupCharacters('abacba'));
// 'aaa,bb,c'

console.log(groupCharacters('abacba', { separator: '-' }));
// 'aaa-bb-c'

console.log(groupCharacters('abacba', { order: 'asc' }));
// 'c,bb,aaa'

console.log(groupCharacters('AaBbCc', { caseSensitive: false }));
// 'aa,bb,cc'

---

使用 reduce 简化

function groupWithReduce(str: string): string {
  return [...str]
    .reduce<Map<string, number>>((map, char) => {
      map.set(char, (map.get(char) || 0) + 1);
      return map;
    }, new Map())
    .entries()
    .toArray()
    .sort((a, b) => b[1] - a[1])
    .map(([char, count]) => char.repeat(count))
    .join(',');
}

提示

ES2024 新增了 Map.prototype.entries().toArray() 方法，但不是所有环境都支持。可以使用 Array.from() 替代。

---

计数排序优化（适用于字符范围有限）

function groupWithCountingSort(str: string): string {
  // 假设只有小写字母
  const counts = new Array(26).fill(0);

  for (const char of str) {
    const index = char.charCodeAt(0) - 97; // 'a' = 97
    if (index >= 0 && index < 26) {
      counts[index]++;
    }
  }

  // 创建 [字符, 次数] 对并排序
  const pairs: Array<[string, number]> = [];

  for (let i = 0; i < 26; i++) {
    if (counts[i] > 0) {
      pairs.push([String.fromCharCode(i + 97), counts[i]]);
    }
  }

  return pairs
    .sort((a, b) => b[1] - a[1])
    .map(([char, count]) => char.repeat(count))
    .join(',');
}

---

性能对比

方法	时间复杂度	空间复杂度	说明
Map 统计	$O(n + k \log k)$	$O(k)$	k 为不同字符数
对象统计	$O(n + k \log k)$	$O(k)$	性能略低于 Map
计数排序	$O(n + k)$	$O(1)$	仅适用于固定字符集

---

常见面试问题

Q1: 如何只返回出现次数超过 1 的字符？

答案：

function groupFrequent(str: string, minCount: number = 2): string {
  const countMap = new Map<string, number>();

  for (const char of str) {
    countMap.set(char, (countMap.get(char) || 0) + 1);
  }

  return Array.from(countMap.entries())
    .filter(([, count]) => count >= minCount)
    .sort((a, b) => b[1] - a[1])
    .map(([char, count]) => char.repeat(count))
    .join(',');
}

console.log(groupFrequent('abacba', 2)); // 'aaa,bb'

Q2: 如何处理包含空格和特殊字符的字符串？

答案：

function groupWithFilter(
  str: string,
  filter: (char: string) => boolean = () => true
): string {
  const countMap = new Map<string, number>();

  for (const char of str) {
    if (filter(char)) {
      countMap.set(char, (countMap.get(char) || 0) + 1);
    }
  }

  return Array.from(countMap.entries())
    .sort((a, b) => b[1] - a[1])
    .map(([char, count]) => char.repeat(count))
    .join(',');
}

// 只统计字母
const isLetter = (c: string) => /[a-zA-Z]/.test(c);
console.log(groupWithFilter('a b!a c@b a', isLetter));
// 'aaa,bb,c'

// 只统计数字
const isDigit = (c: string) => /\d/.test(c);
console.log(groupWithFilter('a1b2c1d1', isDigit));
// '111,2'

Q3: 如何返回 { char: string, count: number }[] 格式？

答案：

interface CharCount {
  char: string;
  count: number;
}

function getCharCounts(str: string): CharCount[] {
  const countMap = new Map<string, number>();

  for (const char of str) {
    countMap.set(char, (countMap.get(char) || 0) + 1);
  }

  return Array.from(countMap.entries())
    .map(([char, count]) => ({ char, count }))
    .sort((a, b) => b.count - a.count);
}

console.log(getCharCounts('abacba'));
// [{ char: 'a', count: 3 }, { char: 'b', count: 2 }, { char: 'c', count: 1 }]

Q4: 如何统计单词频率而不是字符？

答案：

function groupWords(text: string): string {
  const words = text.toLowerCase().match(/\b\w+\b/g) || [];
  const countMap = new Map<string, number>();

  for (const word of words) {
    countMap.set(word, (countMap.get(word) || 0) + 1);
  }

  return Array.from(countMap.entries())
    .sort((a, b) => b[1] - a[1])
    .map(([word, count]) => `${word}(${count})`)
    .join(', ');
}

console.log(groupWords('the quick brown fox jumps over the lazy dog the'));
// 'the(3), quick(1), brown(1), fox(1), jumps(1), over(1), lazy(1), dog(1)'

相关链接

• String.prototype.repeat() - MDN
• Map - MDN
• Array.prototype.sort() - MDN