5. Longest Palindromic Substring

题目

Given a string s, return the longest palindromic substring in s.

Example 1:

1
2
3
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

1
2
Input: s = "cbbd"
Output: "bb"

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters.

题目大意

在给定字符串中找出最长的回文子串（palindromic substring）。回文串是指正读反读都一样的字符串。若存在多个等长的最长回文子串，返回任意一个即可。字符串长度上限为 1000，仅包含数字和英文字母。

你选用何种方法解题？

本题的核心是寻找所有可能回文子串中长度最大的那一个。回文的本质特征是从中心向两侧对称扩展，因此我们有三种主流思路：

方法 核心思路 时间复杂度 说明
方法一：中心扩展法（推荐） 枚举每个可能的回文中心，向外扩展 O(n²) 最优工程解：空间 O(1)、代码简洁、实际运行快
方法二：Manacher 算法 预处理后利用回文对称性跳过重复扩展 O(n) 理论最优：大数据量或竞赛场景的首选
方法三：动态规划 用二维 DP 表记录子串是否回文 O(n²) 空间 O(n²)，仅用于理解回文的递推性质

方法一是推荐解：虽然时间复杂度和 DP 同为 O(n²)，但中心扩展法无需 O(n²) 的额外空间，且实际运行常数因子极小——对于 n = 1000 的上限，最坏仅约 5×10⁵ 次字符比较，远低于 DP 的矩阵填充开销。

Manacher 是理论最优解（O(n)），它的核心洞察非常精彩：预处理插入分隔符统一奇偶回文后，利用已计算回文的对称性，"免费"获取当前中心的初始半径，从而将每个字符的扩展次数均摊为 O(1)。下文会给出完整的手推演算和逐行注释的实现。

解题过程

问题分析

  • 输入：字符串 s，长度 1 ≤ n ≤ 1000
  • 输出：最长的回文子串（任意一个即可）
  • 回文定义：s[l:r+1] 满足 s[l] == s[r], s[l+1] == s[r-1], …，即从两端向中心字符一一相等

核心洞察

回文串的对称轴有两种情况：

  1. 奇数长度（如 "aba"）：对称轴落在一个字符上，中心是 (i, i)
  2. 偶数长度（如 "abba"）：对称轴落在两个字符之间，中心是 (i, i+1)

暴力枚举所有子串需要 O(n³)，但如果固定中心后向外扩展，每个中心只需 O(n)，总共 n 个奇数中心 + n-1 个偶数中心 = 2n-1 个中心，总复杂度 O(n²)。

手推演示例：中心扩展法

以 s = "babad" 为例，追踪算法在每个中心的扩展过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
s = "b a b a d"
     0 1 2 3 4

i=0, 奇数中心 (0,0): expand → "b"            ans = "b"
     偶数中心 (0,1): "ba" 不等 → 无
i=1, 奇数中心 (1,1): expand → "a" → "bab"    ans = "bab" ★
     偶数中心 (1,2): "ab" 不等 → 无
i=2, 奇数中心 (2,2): expand → "b" → "aba"    ans 不变 (len=3)
     偶数中心 (2,3): "ba" 不等 → 无
i=3, 奇数中心 (3,3): expand → "a" → "bad" 不等 → ans 不变
     偶数中心 (3,4): "ad" 不等 → 无
i=4, 奇数中心 (4,4): expand → "d"            ans 不变

最终 ans = "bab"（"aba" 也是等长的合法答案）

关键观察：中心 (1,1) 向外扩展一轮得到 "bab"（长度 3），中心 (2,2) 同样得到 "aba"（长度 3）。两者等长，算法保留先发现的 "bab"。

再以 s = "cbbd" 为例：

1
2
3
4
5
6
7
8
9
10
11
12
s = "c b b d"
     0 1 2 3

i=0, 奇数 (0,0): "c"                           ans = "c"
     偶数 (0,1): "cb" 不等
i=1, 奇数 (1,1): "b"                           ans 不变
     偶数 (1,2): "bb" → 左右越界  ans = "bb" ★
i=2, 奇数 (2,2): "b"                           ans 不变
     偶数 (2,3): "bd" 不等
i=3, 奇数 (3,3): "d"                           ans 不变

最终 ans = "bb"

偶数长度回文的对称轴在字符之间——(1,2) 对应 s[1]='b' 和 s[2]='b' 的中间位置。

手推演示例：Manacher 算法

Manacher 的核心洞察有两个：① 插入 # 统一奇偶回文；② 利用已知回文的对称性，跳过冗余的字符比较。以 s = "babad" 为例逐步追踪。

第一步：预处理——为什么插入 #？

1
2
3
4
5
原串下标:   0   1   2   3   4
原串字符:   b   a   b   a   d

预处理后:   #   b   #   a   #   b   #   a   #   d   #
新下标:     0   1   2   3   4   5   6   7   8   9  10

插入 # 后，所有回文的中心都落在某个确定的数组下标上——原奇数回文 "bab" 的中心是字符 b（在预处理串中也是 b，下标 5），原偶数回文 "abba" 的中心落在两个 b 之间的 # 上。一个统一的下标模型处理两种情况。

定义 p[i] = 以预处理串下标 i 为中心的最长回文半径（不含中心自身）。预处理串中的回文半径 恰好等于 原串中对应回文的长度——这是 Manacher 最优雅的性质。

第二步：核心机制——对称性如何"免费"获取半径？

Manacher 维护两个核心变量：

  • center：当前已知右边界最远的回文中心
  • right：该回文的右边界，即 center + p[center]

对于当前位置 i，设其关于 center 的镜像点 mirror = 2 × center - i：

1
2
3
     mirror          center            i          right
...----|---------------|---------------|------------|----...
       |←——— p[center] ———→|           |←— 待求 —→|

根据 i 与 right 的关系以及 p[mirror] 的大小，分为三种情况：

情况 条件 p[i] 初始值 说明
一：i 在已知回文外 i >= right 0 无对称信息可用，从零开始老老实实扩展
二：镜像回文完全在边界内 i < right 且 p[mirror] < right - i p[mirror] 由于左右完全对称，p[i] 直接等于 p[mirror]，零次扩展
三：镜像回文触及或超出边界 i < right 且 p[mirror] >= right - i right - i p[i] 至少为 right - i，从该值起步继续扩展

这就是 Manacher O(n) 的关键：情况二完全免除了扩展操作，情况三从较大的初始值起步——每个字符平均只扩展常数次。

第三步：完整推演 s = "babad"

预处理串 t = "#b#a#b#a#d#"（长度 11），初始 center=0, right=0, p 全为 0：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
i=0, t[0]='#'
  i >= right(=0) → 情况一: p[0]=0，扩展越界。center=0, right=0

i=1, t[1]='b'
  i >= right(=0) → 情况一: p[1]=0
  扩展: t[0]='#' == t[2]='#' → p[1]=1，再扩越界
  center=1, right=1+1=2  ← 右边界推进

i=2, t[2]='#'
  i >= right(=2) → 情况一: p[2]=0
  扩展: t[1]='b' != t[3]='a'，立即停止
  p[2]=0，right 未推进

i=3, t[3]='a'
  i >= right(=2) → 情况一: p[3]=0
  扩展: t[2]='#'==t[4]='#' → p[3]=1
        t[1]='b'==t[5]='b' → p[3]=2
        t[0]='#'==t[6]='#' → p[3]=3，再扩越界
  center=3, right=3+3=6  ← 右边界大幅推进
  max_center=3, max_len=3

i=4, t[4]='#'
  i < right(=6), mirror=2*3-4=2
  p[mirror]=p[2]=0, right-i=6-4=2
  p[2]=0 < 2 → 情况二: p[4] = p[2] = 0  ← 免费！无需扩展
  验证: t[3]='a' != t[5]='b'，确实不构成更大回文

i=5, t[5]='b'
  i < right(=6), mirror=2*3-5=1
  p[mirror]=p[1]=1, right-i=6-5=1
  p[1]=1 >= 1 → 情况三: p[5] = right - i = 1，从半径1起步扩展
  扩展: t[5-1-1]=t[3]='a' == t[5+1+1]=t[7]='a' → p[5]=2
        t[5-2-1]=t[2]='#' == t[5+2+1]=t[8]='#' → p[5]=3
        t[5-3-1]=t[1]='b' != t[5+3+1]=t[9]='d'，停止
  center=5, right=5+3=8
  p[5]=3 不 > max_len=3，不更新

i=6, t[6]='#'
  i < right(=8), mirror=2*5-6=4
  p[mirror]=p[4]=0, right-i=8-6=2
  p[4]=0 < 2 → 情况二: p[6] = p[4] = 0  ← 免费！

i=7, t[7]='a'
  i < right(=8), mirror=2*5-7=3
  p[mirror]=p[3]=3, right-i=8-7=1
  p[3]=3 >= 1 → 情况三: p[7] = 1，从1起步
  扩展: t[7-1-1]=t[5]='b' != t[7+1+1]=t[9]='d'，停止
  p[7]=1，right 未推进

i=8, t[8]='#'
  i >= right(=8) → 情况一: p[8]=0
  扩展: t[7]='a' != t[9]='d'，立即停止

i=9, t[9]='d'
  i >= right(=8) → 情况一: p[9]=0
  扩展: t[8]='#'==t[10]='#' → p[9]=1，再扩越界
  center=9, right=10

i=10, t[10]='#'
  i >= right(=10) → 情况一: p[10]=0，扩展越界

最终: max_center=3, max_len=3

第四步：映射回原串

max_center=3, max_len=3：

1
2
3
4
5
t = #  b  #  a  #  b  #  a  #  d  #
    0  1  2  3  4  5  6  7  8  9 10
    [-------- p[3]=3 ---------]
    左边界=3-3=0, 中心=3, 右边界=3+3=6
    回文区域: t[0..6] = "#b#a#b#" → 原串 s[0:3] = "bab"

映射公式：start = (max_center - max_len) // 2，长度 = max_len。

1
2
start = (3 - 3) // 2 = 0
ans = s[0:0+3] = "bab" ✓

第五步：对比——Manacher 省了什么？

回顾整个推演，对比中心扩展法（每个中心都从头扩展）：

i 中心扩展法比较次数 Manacher 比较次数 节省原因
0 1 1 无历史信息
1 2 2 无历史信息
2 2 2 无历史信息
3 4 4 无历史信息（首个大回文）
4 2 0 情况二：镜像 p[2]=0 直接复用
5 4 3 情况三：从半径 1 起步（省了首轮）
6 2 0 情况二：镜像 p[4]=0 直接复用
7 3 1 情况三：从半径 1 起步（省了两轮）
8 2 2 回文缩小，无历史可用
9 2 2 无历史信息
10 1 1 无历史信息
总计 25 18 节省约 28%

随着 n 增大且回文密度增加，节省比例会急剧上升——对全相同字符 "aaaa…a"，Manacher 的比较次数为 O(n)，而中心扩展法为 O(n²)。

这些方法具体怎么运用？

方法一：中心扩展法（推荐）

数据结构：无需额外数据结构，仅用两个指针 left 和 right 向两侧扩展。

核心逻辑——内部的 expand 函数：

  1. 接收中心参数 (left, right)，分别代表奇数中心的同一位置 (i, i) 或偶数中心的相邻位置 (i, i+1)
  2. 向外扩展：当 left >= 0 且 right < n 且 s[left] == s[right] 时，left -= 1, right += 1
  3. 循环结束时 left 和 right 停在回文区域之外一步，因此合法回文子串为 s[left+1 : right]

边界情况处理：

场景 输入示例 行为 结果
单字符串 "a" 奇数中心扩展一次即越界 "a"
全相同字符 "aaaa" 多个中心扩展出不同长度的回文，取最长 "aaaa"
无回文（长度 > 1） "ab" 所有中心扩展均只有单字符回文 "a" 或 "b"
最长回文在末尾 "abcba" 中心 (2,2)="c" 扩展出 "abcba" "abcba"
偶数回文比奇数长 "cbbd" 偶数中心 (1,2) 发现 "bb"，奇数中心最多 "b" "bb"

expand 返回切片的解释：

1
2
3
4
5
def expand(left, right):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return s[left + 1:right]  # 最后一次 while 体执行后 left 和 right 多走了一步

最后一次匹配成功时 left 和 right 各向外多走了一步（不匹配或越界），所以回文区域是 (left+1, right-1) 闭区间，Python 切片 s[left+1:right] 正好对应左闭右开。

方法二：Manacher 算法

预处理：插入分隔符 #

1
2
# "babad" → "#b#a#b#a#d#"
t = "#" + "#".join(s) + "#"

为什么首尾也要加 #？确保预处理串长度恒为奇数（2n+1），从而每个回文的中心都恰好落在一个字符上。同时，首尾的 # 充当哨兵，扩展时自然越界，无需额外边界判断。

核心逻辑：三步循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
对于预处理串的每个位置 i：

  Step 1 — 利用对称性，获取初始半径
  ┌─────────────────────────────────────────┐
  │ mirror = 2 × center - i                 │
  │ if i < right:                           │
  │     p[i] = min(right - i, p[mirror])    │  ← 情况二/三：复用历史
  │ else:                                   │
  │     p[i] = 0                            │  ← 情况一：从零开始
  └─────────────────────────────────────────┘
         ↓
  Step 2 — 基于初始半径，尝试向外扩展
  ┌─────────────────────────────────────────┐
  │ while t[i - p[i] - 1] == t[i + p[i] + 1]: │
  │     p[i] += 1                           │
  └─────────────────────────────────────────┘
         ↓
  Step 3 — 更新 center 和 right（维护"最右回文"）
  ┌─────────────────────────────────────────┐
  │ if i + p[i] > right:                    │
  │     center = i                          │
  │     right = i + p[i]                    │
  └─────────────────────────────────────────┘

关键细节解析

为什么 p[i] = min(right - i, p[mirror])？

right - i 是 i 到已知回文右边界的距离——我们对边界外的字符一无所知，所以初始半径不能超过这个距离。p[mirror] 是镜像位置的回文半径。取两者最小值：

  • 若 p[mirror] < right - i：镜像回文完全被已知回文包裹，由对称性直接得 p[i] = p[mirror]
  • 若 p[mirror] >= right - i：镜像回文可能延伸到已知回文之外，但 i 侧对应位置的字符尚未验证，保守取 right - i

为什么扩展循环用 t[i - p[i] - 1] 而不是 t[i - p[i]]？

p[i] 是已知半径，下一对待比较的字符在 p[i] + 1 的位置。例如 p[i]=2 时已经确认 t[i-2] 到 t[i+2] 是回文，现在检查 t[i-3] 和 t[i+3]。

为什么映射公式是 (max_center - max_len) // 2？

预处理串长度为 2n+1。在预处理串中，回文区域为 [max_center - max_len, max_center + max_len]。这个区间内的原串字符对应于 t 中下标为奇数的位置 1, 3, 5, …。区间内有 max_len 个原串字符（因为 # 和原字符交替，且半径恰好等于原串回文长度），起始原串下标为 (max_center - max_len) // 2。这个公式在奇偶回文上都正确，无需分情况讨论。

边界情况

场景 输入 Manacher 行为 结果
空串 "" 直接返回 "" ""
单字符 "a" 预处理 "#a#"，p[1]=1，映射 s[0:1] "a"
全相同 "aaaa" p 数组持续扩大，中心在一处即可覆盖全串 "aaaa"
全不同 "abcd" 每个位置 p[i] 仅为 0 或 1，无 O(n) 加速 "a"

方法三：动态规划

数据结构：dp[i][j] 表示 s[i:j+1] 是否为回文串。dp 是一个 n × n 的布尔矩阵。

状态转移：

  • dp[i][j] = True 当且仅当 s[i] == s[j] 且（j - i < 3 或 dp[i+1][j-1] == True）
  • j - i < 3 意味着子串长度为 1、2 或 3——长度 ≤ 3 时只需两端字符相等

核心逻辑：

  1. 初始化：所有 dp[i][i] = True（单字符回文）
  2. 按子串长度从小到大递推：先处理长度为 2、再 3、…、n
  3. 每次发现更长的回文子串时更新答案

缺点：需要 O(n²) 空间存储整个 DP 表，且必须填充 n²/2 个格子，常数因子显著大于中心扩展法。对于 n = 1000，DP 表约占 1MB 内存，虽可接受但无必要。

复杂度

方法 时间复杂度 空间复杂度 说明
中心扩展法 O(n²) O(1) 2n-1 个中心，每个中心最坏扩展 n/2 步
Manacher O(n) O(n) 内层 while 的扩展次数均摊 O(1) 每字符
动态规划 O(n²) O(n²) 填满半个 n×n 矩阵，无法优化空间至 O(1)

中心扩展法复杂度详析：

  • 最坏情况（如全相同字符 "aaaa…a"）：每个中心的扩展都进行到边界为止，第 k 个中心扩展约 min(k, n-k) 步，总比较次数 ≈ n²/4
  • 最好情况（如 "abcd…z" 无回文）：每个中心仅比较一次即失败，总比较次数 ≈ 2n-1 = O(n)
  • 平均情况：在随机英文文本中，大多数中心在第一轮就因字符不匹配而停止，实际运行接近 O(n)

Manacher 复杂度详析——为什么内层 while 不会导致 O(n²)？

内层 while 每成功扩展一次，right 必然向右移动一位（因为 i + p[i] 增加了）。而 right 最多从 0 走到 n-1，总共移动 O(n) 次。失败扩展（不匹配）每轮最多发生一次。因此总比较次数严格 ≤ 2n。

换句话说：每个字符最多被成功匹配一次（推进 right），最多被失败匹配一次（停止扩展），从而均摊 O(1)。

总结与最佳选择

最快算法：

  • n ≤ 10³（LeetCode 约束）：中心扩展法实际最快（< 5ms），常数因子极小。Manacher 的预处理和复杂分支逻辑在此规模下反而拖累性能。
  • n ≥ 10⁵（大数据/竞赛场景）：Manacher 是唯一可行的线性解。中心扩展法的 O(n²) 在此规模下完全不可用（10¹⁰ 次操作 → 数秒甚至数十秒）。

工程最优选择：中心扩展法（方法一），理由：

  1. 空间 O(1)：不需要任何额外数组，原地操作
  2. 代码极简：核心逻辑仅 7 行，5 分钟内写出无 bug
  3. LeetCode 实际最快：n ≤ 1000 下跑完所有测试用例在 5ms 以内
  4. 可扩展性：稍加修改即可同时返回所有最长回文子串或统计回文子串总数

各方法的使用场景：

场景 推荐方法 理由
LeetCode / 面试 中心扩展法 最短代码、最直观思路、空间 O(1) 是加分项
大数据量（n ≥ 10⁵） Manacher O(n) 是唯一选择，O(n²) 在这个量级不可接受
学习回文递推 动态规划 为回文分割、回文子序列等变种题打基础
竞赛（n 不明确） Manacher 永远不超时，不用估数据规模

一句话：面试写中心扩展（稳），竞赛用 Manacher（快），DP 用来理解回文递推（学）。

Code

方法一：中心扩展法（推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def longestPalindrome(self, s: str) -> str:
        """中心扩展法：枚举每个可能的回文中心，向两侧扩展。
        奇数中心 (i, i) 和偶数中心 (i, i+1) 分别处理。
        时间复杂度 O(n²)，空间复杂度 O(1)。
        """
        ans = ""

        def expand(left: int, right: int) -> str:
            """以 left, right 为中心向两侧扩展，返回最长回文子串。"""
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # 循环结束时 left 和 right 在回文区域之外一步
            return s[left + 1:right]

        for i in range(len(s)):
            # 奇数长度回文：中心是单个字符 s[i]
            p1 = expand(i, i)

            # 偶数长度回文：中心是 s[i] 和 s[i+1] 之间
            p2 = expand(i, i + 1)

            # 保留更长的回文串
            if len(p1) > len(ans):
                ans = p1
            if len(p2) > len(ans):
                ans = p2

        return ans

方法二：Manacher 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution:
    def longestPalindrome(self, s: str) -> str:
        """Manacher 算法：预处理插入 '#' 统一奇偶回文，利用对称性线性扩展。
        时间复杂度 O(n)，空间复杂度 O(n)。
        适合 n ≥ 10⁵ 的大数据量或竞赛场景。
        """
        if not s:
            return ""

        # ── 第一步：预处理 ──
        # 插入 '#' 分隔符，使所有回文中心都落在确定的数组下标上
        # "abc" → "#a#b#c#"，长度从 n 变为 2n+1（恒为奇数）
        t = "#" + "#".join(s) + "#"
        n = len(t)                      # 预处理串长度 = 2 × len(s) + 1

        # p[i] = 以 t[i] 为中心的最长回文半径（不含中心自身）
        # 重要性质：p[i] 恰好等于原串中对应回文的长度
        p = [0] * n

        center = 0                      # 当前右边界最远的回文中心
        right = 0                       # 该回文的右边界 = center + p[center]
        max_center = 0                  # 全局最长回文的中心下标
        max_len = 0                     # 全局最长回文半径（= 原串回文长度）

        # ── 第二步：逐位置计算回文半径 ──
        for i in range(n):
            # Step 2.1：利用对称性，获取初始半径（避免重复扩展）
            mirror = 2 * center - i     # i 关于 center 的对称点
            if i < right:
                # 情况二/三：i 在已知回文范围内，可复用镜像信息
                p[i] = min(right - i, p[mirror])
            else:
                # 情况一：i 在已知回文外，从零开始
                p[i] = 0

            # Step 2.2：基于初始半径，尝试向外扩展
            # 检查 p[i]+1 距离处的字符对
            while (i - p[i] - 1 >= 0 and i + p[i] + 1 < n
                   and t[i - p[i] - 1] == t[i + p[i] + 1]):
                p[i] += 1

            # Step 2.3：维护"最右回文"——右边界越远，后续可复用的信息越多
            if i + p[i] > right:
                center = i
                right = i + p[i]

            # Step 2.4：更新全局最长回文
            if p[i] > max_len:
                max_len = p[i]
                max_center = i

        # ── 第三步：映射回原串 ──
        # 公式推导：预处理串中回文区域的左边界 = max_center - max_len
        # 该位置对应原串下标 = (max_center - max_len) // 2
        # 原因：预处理串中位置 j 对应原串位置 j//2（当 j 为奇数时是原字符）
        start = (max_center - max_len) // 2
        return s[start:start + max_len]

方法三：动态规划（仅供对比）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
    def longestPalindrome(self, s: str) -> str:
        """动态规划：dp[i][j] 表示 s[i:j+1] 是否为回文。
        按子串长度从小到大递推。
        时间复杂度 O(n²)，空间复杂度 O(n²)。
        """
        n = len(s)
        if n < 2:
            return s

        # dp[i][j]: s[i:j+1] 是否为回文串
        dp = [[False] * n for _ in range(n)]
        start, max_len = 0, 1

        # 所有长度为 1 的子串都是回文
        for i in range(n):
            dp[i][i] = True

        # 按子串长度 L 从小到大递推
        for L in range(2, n + 1):           # L: 子串长度
            for i in range(n - L + 1):      # i: 子串起始位置
                j = i + L - 1               # j: 子串结束位置

                if s[i] != s[j]:
                    dp[i][j] = False
                else:
                    # 长度 ≤ 3 时只需两端相等；更长时需内部也是回文
                    if j - i < 3:
                        dp[i][j] = True
                    else:
                        dp[i][j] = dp[i + 1][j - 1]

                if dp[i][j] and L > max_len:
                    start = i
                    max_len = L

        return s[start:start + max_len]