#P4547. 第2题-基于样本纯净度指标的大模型训练数据清洗方法
-
1000ms
Tried: 103
Accepted: 26
Difficulty: 5
所属公司 :
华为
时间 :2026年1月21日-AI方向
-
算法标签>双指针
第2题-基于样本纯净度指标的大模型训练数据清洗方法
解题思路
这题要求计算字符串中“最长无重复字符的连续子串”的长度,本质是经典问题:最长不含重复字符的子串。
可用滑动窗口(双指针)+ 记录字符上一次出现位置来做,保证线性时间。
核心做法:
-
维护窗口左端
l,遍历右端r从左到右扫描字符串。 -
用数组/哈希表
last[c]记录字符c最近一次出现的下标(初始化为 -1)。 -
当扫描到字符
c = s[r]:- 若
last[c] >= l,说明c在当前窗口内重复了,需要把左端移动到last[c] + 1,从而去掉重复。 - 更新
last[c] = r。 - 当前窗口长度为
r - l + 1,更新答案最大值。
- 若
-
因为字符集是 ASCII(最多 128/256),用定长数组代替哈希表更快更省内存。
实现要点:
- n 可到 1e7,必须 O(n) 扫描一次。
- Python/Java/C++ 都要用高效输入方式读取整行字符串(无空格)。
last用大小 256 的数组,按ord(ch)/(unsigned char)映射索引。
复杂度分析
- 时间复杂度:O(n),每个字符最多被右指针访问一次,左指针单调递增。
- 空间复杂度:O(V),V 为字符集大小(ASCII 取 256),与 n 无关,满足要求。
代码实现
import sys
def longest_unique_substring_len(s: str) -> int:
# ASCII 字符集,开 256 大小数组记录最近出现位置
last = [-1] * 256
l = 0
ans = 0
# 遍历右端指针 r
for r, ch in enumerate(s):
idx = ord(ch) # 将字符映射到 0~255
# 如果该字符上次出现位置在当前窗口内,移动左端去重
if last[idx] >= l:
l = last[idx] + 1
# 更新该字符最近出现位置
last[idx] = r
# 更新答案
cur_len = r - l + 1
if cur_len > ans:
ans = cur_len
return ans
def main():
s = sys.stdin.readline().strip()
if not s:
return
print(longest_unique_substring_len(s))
if __name__ == "__main__":
main()
#include <bits/stdc++.h>
using namespace std;
int longest_unique_substring_len(const string &s) {
// ASCII 字符集,使用 256 大小数组记录最近出现位置
int last[256];
for (int i = 0; i < 256; i++) last[i] = -1;
int l = 0;
int ans = 0;
// 遍历右端指针 r
for (int r = 0; r < (int)s.size(); r++) {
unsigned char c = (unsigned char)s[r]; // 防止 char 为负导致索引越界
// 若该字符在当前窗口内重复,移动左端
if (last[c] >= l) {
l = last[c] + 1;
}
// 更新最近出现位置
last[c] = r;
// 更新答案
int curLen = r - l + 1;
if (curLen > ans) ans = curLen;
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
if (!(cin >> s)) return 0;
cout << longest_unique_substring_len(s) << "\n";
return 0;
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static int longestUniqueSubstringLen(String s) {
// ASCII 字符集,使用 256 大小数组记录最近出现位置
int[] last = new int[256];
// 初始化为 -1,表示从未出现
for (int i = 0; i < 256; i++) last[i] = -1;
int l = 0;
int ans = 0;
// 遍历右端指针 r
for (int r = 0; r < s.length(); r++) {
int idx = (int) s.charAt(r); // char 可直接转为 0~65535,这里题面保证 ASCII
// 若该字符在当前窗口内重复,移动左端
if (last[idx] >= l) {
l = last[idx] + 1;
}
// 更新最近出现位置
last[idx] = r;
// 更新答案
int curLen = r - l + 1;
if (curLen > ans) ans = curLen;
}
return ans;
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = br.readLine();
if (s == null || s.length() == 0) return;
System.out.println(longestUniqueSubstringLen(s.trim()));
}
}
题目内容
在大规模文本语料收集和 OCR处理环节,常会在每条样本中残留重复的页眉、页脚、广告标记或爬虫抓取时的模板片段,这些重复内容对模型训练质量影响极大。我们考虑一个简化的场景:我们希望用 “最长无重复子字符串”(即样本中最长的一段不含任何重复字符的连续片段)来量化一条文本的 “纯净度”。直观地讲,最长无重复子串越短,说明这条样本中重复噪声越严重,越应优先清洗或剔除。
给定一条原始文本样本 s,其中可能包含大量重复的页眉 / 页脚或爬虫模板噪声。请你计算并返回其最长无重复字符子串的长度,作为该样本的 “纯净度指标”。
输入
字符串s,由 ASCII字母、数字构成。不会有空格。长度n(1≤n≤107)
输出
一个整数,表示s 中最长的不含重复字符的子串的长度
样例 1
输入:
aA1aA1bB2
输出:
6
说明
最长非重复内容为 aA1bB2
样例2
输入:
tttttttttt
输出:
1
说明
重复同一个字符,最长子字符串为 b
提示
尝试使用时间复杂度 O (n),空间复杂度 O (min (n, V))(其中 V 为字符集大小),否则可能无法拿到全部分数