TypeScript 类型级游程编码（Run-length Encoding）实战：type-challenges 14188 的 Encode / Decode 类型实现精解

本篇文章以 type-challenges 仓库中编号 14188 的 hard 级挑战 Run-length encoding 为研究对象，完整剖析如何在 TypeScript 类型系统中用模板字面量类型与递归实现游程编码（Run-length Encoding）的编码器 Encode<S> 与解码器 Decode<S>。读完本文，你将掌握类型级字符串逐字符拆解、连续字符分组计数、数字串读取与字符重复展开的完整套路，并能举一反三应用到仓库中其他字符串处理类挑战（如 Split、DropChar、PercentageParser 等）。

一、题目速览：14188 Run-length encoding

该挑战位于仓库 questions/14188-hard-run-length-encoding，由 Hen Hedymdeith（GitHub 账号 @alfaproxima）提出，在 info.yml 中标记的难度为 hard。

原文档给出的需求非常精炼，原文如下：

Given a string sequence of a letters f.e. AAABCCXXXXXXY. Return run-length encoded string 3AB2C6XY. Also make a decoder for that string.

即：给定一个由字母组成的字符串序列，返回其游程编码（Run-length encoded）字符串；同时还需要为该编码串实现解码器。文档给出的唯一一组编码/解码示例为：

方向	输入	输出
编码 Encode	AAABCCXXXXXXY	3AB2C6XY
解码 Decode	3AB2C6XY	AAABCCXXXXXXY

需要在 template.ts 中补齐的类型签名如下：

namespace RLE {
  export type Encode<S extends string> = any
  export type Decode<S extends string> = any
}

对应的测试用例定义在 test-cases.ts 中：

import type { Equal, Expect } from '@type-challenges/utils'

type cases = [
  // Raw string -> encoded string
  Expect<Equal<RLE.Encode<'AAABCCXXXXXXY'>, '3AB2C6XY'>>,

  // Encoded string -> decoded string
  Expect<Equal<RLE.Decode<'3AB2C6XY'>, 'AAABCCXXXXXXY'>>,
]

二、先把游程编码的规则读透

在动手写类型之前，必须先把字符串层面的算法规则弄清楚，否则类型实现的每一步都会出错。

把 AAABCCXXXXXXY 从左到右扫描，按"连续相同字符"分组：

连续段	长度	编码结果
AAA	3	3A
B	1	B
CC	2	2C
XXXXXX	6	6X
Y	1	Y

拼接得到 3AB2C6XY。可见本挑战的规则是：

1. 连续出现 ≥ 2 次的字符：编码为「出现次数（十进制数字串）+ 字符」，如 AAA → 3A、CC → 2C、XXXXXX → 6X；
2. 仅出现 1 次的字符：原样输出，不加数字前缀，如 B → B、Y → Y。

解码是编码的逆过程：遇到数字前缀 N 时，将紧随其后的单个字符展开 N 次；没有数字前缀的字符直接透传。因此 3AB2C6XY 展开为 AAA + B + CC + XXXXXX + Y = AAABCCXXXXXXY。

两个值得注意的工程细节（虽然测试用例没有覆盖，但设计类型时应心中有数）：

• 数字前缀可以是多位数（例如 12X 表示 12 个 X），解码器应能完整读取整段数字，而不是只读一位；
• 数字前缀后的字符按题意总是存在的，但实现时可以决定对"数字后无字符"这类非法输入采取何种策略（本文采用返回 never 的保守做法）。

三、类型级字符串处理的基础设施

要实现这个挑战，需要用到 TypeScript 类型系统中两个最核心的"字符串处理"能力：模板字面量类型与 infer 递归。它们在本仓库中是一系列字符串类挑战的共同基础设施，例如：

• 02822-hard-split：用分隔符切分字符串，其核心同样是 S extends ${infer Head}${infer Tail}`` 式的逐字符递归；
• 02070-medium-drop-char：删除字符串中的指定字符；
• 00298-medium-length-of-string：用元组计数统计字符串长度；
• 00119-medium-replaceall：全局替换子串；
• 01978-medium-percentage-parser：解析百分号字符串中的数字与符号，同样涉及"读取数字串"的类型逻辑。

下面简述本挑战将用到的三个基本功。

1. 逐字符拆分：infer + 模板字面量

type SplitHead<S extends string> = S extends `${infer Head}${infer Tail}`
  ? [Head, Tail]   // 例如 'ABC' -> ['A', 'BC']
  : never

模板字面量类型里的 infer Head 默认匹配一个字符，infer Tail 匹配剩余部分。当字符串为空时，条件不成立，从而形成递归的终止分支。

2. 条件判断：某字符是否为数字

type IsDigit<C extends string> = C extends `${number}` ? true : false

TS 内置的 ${number} 模板类型可以匹配任何合法的十进制数字表示。单个数字字符（0~9）都能匹配成功，而字母字符不会。

3. 用元组长度做"计数"

类型系统里没有可变的 number 变量，计数通常借助元组的 length 属性：每"数一次"就往元组里追加一个元素，最终 T['length'] 就是精确的字面量数字类型。例如统计字符串长度：

type LengthOf<S extends string, T extends string[] = []> =
  S extends `${string}${infer Rest}`
    ? LengthOf<Rest, [...T, string]>
    : T['length']

LengthOf<'AAA'> 会精确地得到字面量类型 3，进而 ${LengthOf<'AAA'>} 得到 '3'。这正是 Encode 中把"出现次数"写成数字前缀的手段。

四、实现 Encode：把连续字符折叠成游程

分步拆解

编码过程可以分解为三个子问题：

1. 分组：从串首提取出连续相同字符构成的一段（如 AAA），并得到剩余串；
2. 计段：统计该段的长度；若长度 ≥ 2 则带上数字前缀，否则原样输出该字符；
3. 递归：对剩余串重复上述过程。

参考实现

namespace RLE {
  // ── 1. 从 S 开头截取与 C 连续相同的字符段 ──
  // 返回 [连续段, 剩余串]，例如 TakeRun<'A', 'AAABCC'> -> ['AAA', 'BCC']
  type TakeRun<C extends string, S extends string, Acc extends string = C> =
    S extends `${C}${infer Rest}`
      ? TakeRun<C, Rest, `${Acc}${C}`>
      : [Acc, S]

  // ── 2. 计算字符串的字面量长度 ──
  type Length<S extends string, T extends string[] = []> =
    S extends `${string}${infer Rest}`
      ? Length<Rest, [...T, string]>
      : T['length']

  // ── 3. 根据连续段长度决定是否加数字前缀 ──
  // 'AAA' -> '3A'; 'B' -> 'B'; 'CC' -> '2C'
  type EncodeRun<C extends string, Run extends string> =
    Run extends `${C}${C}${string}`      // 连续出现 >= 2 次
      ? `${Length<Run>}${C}`
      : C                                // 只出现 1 次，原样输出

  // ── 4. 编码主体：递归处理每一段 ──
  export type Encode<S extends string> = S extends `${infer C}${string}`
    ? TakeRun<C, S> extends [infer Run extends string, infer Rest extends string]
      ? `${EncodeRun<C, Run>}${Encode<Rest>}`
      : never
    : S
}

逐行讲解

TakeRun 是本实现的关键。它以首字符 C 为参照，只要剩余串仍以 C 开头就继续累积进 Acc，直到遇到第一个不同的字符为止：

• 输入 'AAABCCXXXXXXY'，首字符 C = 'A'；
• 递归过程：Acc 依次变为 'A' → 'AA' → 'AAA'，遇到 'B' 后停止，返回 ['AAA', 'BCCXXXXXXY']。

EncodeRun 用 Run extends ${C}${C}${string}`` 判断连续段是否至少 2 个字符。注意这里刻意没有直接比较长度数字，而是利用模板匹配：

• Run = 'AAA' 能匹配"两个 C 再加任意内容" → 输出 3A；
• Run = 'B' 不能匹配 → 原样输出 B；
• Run = 'CC' 能匹配 → 输出 2C。

之所以用模板匹配而不是 Length<Run> extends 1 之类的判断，是因为字面量长度的比较在类型层面更繁琐，模板匹配表达"至少两个字符"更加直接可靠。

Encode 主循环：只要串非空，就取出首字符 C，用 TakeRun 切出一段，把 EncodeRun 的结果与对剩余串递归的结果拼接。空串 '' 无法匹配 ${infer C}${string}，直接返回自身，成为终止分支。

沿 'AAABCCXXXXXXY' 手工推演一遍完整流程：

Encode<'AAABCCXXXXXXY'>
  TakeRun<'A', ...> → ['AAA', 'BCCXXXXXXY']
  EncodeRun<'A', 'AAA'> → '3A'
  + Encode<'BCCXXXXXXY'>
      → 'B' + Encode<'CCXXXXXXY'>
          → '2C' + Encode<'XXXXXXY'>
              → '6X' + Encode<'Y'>
                  → 'Y'
 结果：'3A' + 'B' + '2C' + '6X' + 'Y' = '3AB2C6XY'  ✓

五、实现 Decode：把游程展开为原始串

分步拆解

解码同样拆成三个子问题：

1. 读数字：从串首连续读取数字位，直到遇到非数字字符，得到完整的十进制数字串 N 与剩余串；
2. 展开：把紧随数字之后的那个字符重复 N 次；
3. 递归：对剩余串继续解码；若当前字符不是数字，则原样透传并继续。

参考实现

namespace RLE {
  // ── 1. 从串首读取完整数字串 ──
  // ReadNum<'3AB2C6XY'> -> ['3', 'AB2C6XY']；ReadNum<'12X'> -> ['12', 'X']
  type ReadNum<S extends string, Acc extends string = ''> =
    S extends `${infer D}${infer Rest}`
      ? D extends `${number}`
        ? ReadNum<Rest, `${Acc}${D}`>
        : [Acc, S]
      : [Acc, S]

  // ── 2. 把字符 C 重复 N 次（N 为十进制数字字符串）──
  // Repeat<'A', '3'> -> 'AAA'
  type Repeat<
    C extends string,
    N extends string,
    Acc extends string = '',
    Count extends string[] = []
  > =
    `${Count['length']}` extends N
      ? Acc
      : Repeat<C, N, `${Acc}${C}`, [...Count, string]>

  // ── 3. 解码主体 ──
  export type Decode<S extends string> = S extends `${infer Head}${infer Tail}`
    ? Head extends `${number}`
      ? ReadNum<S> extends [infer N extends string, infer Rest extends string]
        ? Rest extends `${infer C}${infer _}`
          ? `${Repeat<C, N>}${Decode<Rest>}`
          : never   // 非法输入：数字后没有字符
        : never
      : `${Head}${Decode<Tail>}`
    : S
}

逐行讲解

ReadNum 逐位累积数字。Acc 初始为空，每遇到一个数字字符就追加到 Acc 尾部；一旦遇到非数字字符，立即返回 [Acc, S]（注意返回的是当前的完整剩余串 S，而不是 Rest，因为 Rest 在上一轮已被消费）。这样即使编码中出现 12X 这种多位数，也能一次性读出 '12'。

Repeat 是"用元组长度计数"的典型应用。Count 每递归一次追加一个元素，比较 ${Count['length']} 与目标数字串 N：

• 相等 → 返回累积出的 Acc（终止）；
• 不等 → 继续在 Acc 尾部追加一个 C，同时 Count 加一。

以 Repeat<'A', '3'> 为例，递归过程为：'0'≠'3' → Acc='A'、Count=['']；'1'≠'3' → Acc='AA'、Count=['','']；'2'≠'3' → Acc='AAA'、Count=['','','']；'3'='3' → 返回 'AAA'。

Decode 主循环先看当前字符 Head：

• 是数字 → 用 ReadNum 读出完整数字串 N，再从 Rest 中取出第一个字符 C，用 Repeat<C, N> 展开，然后递归解码 Rest（注意这里递归传入的是 Rest，它仍然包含字符 C 本身，但 Repeat 已经消费了它，因此不会重复输出）；
• 不是数字 → 原样透传 Head，对 Tail 继续递归；
• 空串 → 返回自身，终止。

沿 '3AB2C6XY' 手工推演：

Decode<'3AB2C6XY'>
  Head='3' 是数字 → ReadNum → N='3', Rest='AB2C6XY'
  C='A' → Repeat<'A','3'> = 'AAA'
  + Decode<'AB2C6XY'>
      → 'A' + Decode<'B2C6XY'>
          → 'B' + Decode<'2C6XY'>
              → Repeat<'C','2'> = 'CC' + Decode<'6XY'>
                  → Repeat<'X','6'> = 'XXXXXX' + Decode<'Y'>
                      → 'Y'
 结果：'AAA' + 'A' + 'B' + 'CC' + 'XXXXXX' + 'Y' = 'AAABCCXXXXXXY'  ✓

六、用仓库测试用例验证实现

test-cases.ts 中通过 Equal 与 Expect 两个工具类型对结果做编译期断言：

Expect<Equal<RLE.Encode<'AAABCCXXXXXXY'>, '3AB2C6XY'>>
Expect<Equal<RLE.Decode<'3AB2C6XY'>, 'AAABCCXXXXXXY'>>

这两个工具定义在仓库 utils/index.d.ts 中。其中 Equal 的实现值得注意——它利用"同一泛型函数在不同实例化下是否可互相赋值"来检测两个类型是否结构上完全相同（而不是单向可赋值）：

export type Equal<X, Y> =
  (<T>() => T extends X ? 1 : 2) extends
  (<T>() => T extends Y ? 1 : 2) ? true : false

export type Expect<T extends true> = T

Expect<T extends true> 强制断言必须是 true 字面量类型：一旦你的 Encode / Decode 推导结果与期望不一致，编译器就会在这一行报错。因此可以直接在本地执行 tsc --noEmit（或直接在编辑器中打开 test-cases.ts）来验证上面给出的实现是否正确通过这两个方向上的断言。

七、边界情况与健壮性讨论

从上面的实现出发，可以进一步确认它在以下边界输入下的行为：

• 空字符串：Encode<''> 与 Decode<''> 均返回 ''。模板匹配 ${infer C}${string} / ${infer Head}${infer Tail} 对空串不成立，直接落入终止分支；
• 全是单字符的输入：例如 Encode<'ABC'> → 'ABC'，因为每段长度都是 1，EncodeRun 均走原样输出分支；
• 多位数前缀：Decode<'12X'> 可正确得到 12 个 X，因为 ReadNum 会连续读取 '1' 与 '2' 拼成 '12'；
• 非法输入（数字后无字符）：Decode<'3'> 在 Rest extends ${infer C}${infer _}`` 分支失败，返回 never。这是一种"显式拒绝"的策略，避免静默产出错误类型。

同时需要了解类型系统本身的限制（这属于实践中的常识，可从实现结构推断）：Repeat 的递归层数等于目标数字的大小，Length 与 TakeRun 的递归层数等于字符串长度，二者都会受到编译器递归深度上限的约束。对于本挑战测试用例这种几十个字符以内的字符串完全够用；若遇到极长输入，则要考虑用"翻倍展开"之类的技巧降低递归深度。

八、延伸：同一仓库中的类型级字符串挑战

掌握了本挑战的三大核心技巧——模板字面量拆解、infer 递归、元组长度计数——你会发现仓库中大量字符串类挑战共享同一套思维模式：

挑战	核心技巧	与本挑战的关联
02822-hard-split	按分隔符递归切分字符串	与 TakeRun 同源的"前缀匹配 + 递归消费"模式
02070-medium-drop-char	逐字符判断是否删除	与 Encode 的逐字符主循环同构
00298-medium-length-of-string	元组计数字符串长度	与 Length / Repeat 的计数手段一致
00119-medium-replaceall	查找子串并递归替换	复用 S extends ${P}${infer Rest}`` 式匹配
01978-medium-percentage-parser	读取符号、数字与百分号	其中的数字读取逻辑与 ReadNum 一脉相承

九、小结

本文以 questions/14188-hard-run-length-encoding 为骨架，完整还原了在 TypeScript 类型系统中实现游程编码的全过程：

• 编码器 Encode<S>：通过 TakeRun 对连续相同字符分组、Length + 模板匹配判断是否需要数字前缀，最后递归拼接，把 AAABCCXXXXXXY 压缩为 3AB2C6XY；
• 解码器 Decode<S>：通过 ReadNum 完整读取数字前缀、Repeat 用元组长度计数展开字符，把 3AB2C6XY 还原为 AAABCCXXXXXXY。

两道类型都通过了 test-cases.ts 中基于 utils/index.d.ts 的 Equal / Expect 编译期断言。这套"模板字面量拆解 + infer 递归 + 元组计数"的组合拳，是攻克仓库内绝大多数 hard 级字符串挑战的通用武器。