小欧的前后缀交换
小欧的前后缀交换
OPPO 笔试真题 · 2024 秋招 · 移动端
判题请到牛客原题提交。
题目描述
小欧拿到了一个仅由'o'和'p'组成的字符串。
她希望将前缀尽可能多的连续'o'和后缀尽可能多的连续'p'交换一次。
你能帮帮她吗？
字符串的前缀：符号串左部的任意子串（或者说是字符串的任意首部）
字符串的后缀：符号串右部的任意子串（或者说是字符串的任意尾部）
输入格式
一行字符串，仅由'o'和'p'组成。
保证字符串的长度不超过100000
输出格式
交换后的字符串。
示例
示例 1
输入：
ooppoopp输出：
ppppoooo示例 2
输入：
ooooop输出：
pooooo示例 3
输入：
ppppopo输出：
ppppopo解题思路
第一步：理解问题本质
字符串只有 'o' 和 'p' 两种字符。题目圈出两段：
- 前缀：从第 1 个字符开始，尽可能多的连续
'o'； - 后缀：从最后一个字符开始，尽可能多的连续
'p'。
把这两段整体互换（前缀那段挪到末尾，后缀那段挪到开头），中间不参与交换的部分保持原样。
注意两段长度不一定相等，题目没有这个要求。
第二步：先数清楚两段有多长
- 前缀
'o'的个数i：从下标 0 往右数，遇到不是'o'的字符就停； - 后缀
'p'的个数j：从下标n-1往左数，遇到不是'p'的字符就停。
两段不可能重叠：前缀里的字符全是 'o'，后缀里的字符全是 'p'，
一个位置不可能同时属于两段（否则它既是 'o' 又是 'p'）。
第三步：按「交换后长什么样」直接拼
交换之后：
- 开头变成原来的后缀，即
j个'p'； - 中间是原来的
s[i : n-j]，一个字都不变； - 结尾变成原来的前缀，即
i个'o'。
所以结果可以直接写成一行的拼接：
'p' * j + s[i : n - j] + 'o' * i不需要真的去做「切下来再交换」，按长度拼出来既简单又不会出现切片越界。
完整代码实现
import sys
def solve() -> None:
"""数出前缀 'o' 与后缀 'p' 的长度，拼出交换后的字符串"""
data = sys.stdin.buffer.read().split()
if not data:
return
s = data[0].decode()
n = len(s)
i = 0
while i < n and s[i] == 'o': # 前缀连续 'o' 的个数
i += 1
j = 0
while j < n and s[n - 1 - j] == 'p': # 后缀连续 'p' 的个数
j += 1
result = 'p' * j + s[i:n - j] + 'o' * i
sys.stdout.write(result + "\n")
if __name__ == "__main__":
solve()示例推演
示例 1：s = "ooppoopp"，长度 n = 8。
| 位置 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 字符 | o | o | p | p | o | o | p | p |
- 前缀连续
'o'：位置 0、1，共i = 2个； - 后缀连续
'p'：位置 7、6，共j = 2个； - 中间段
s[2 : 6] = "ppoo"。
拼接：'pp' + "ppoo" + 'oo' = "ppppoooo"，与样例输出一致。
示例 2：s = "ooooop"，n = 6。
- 前缀
'o'：位置 0~4，共i = 5个； - 后缀
'p'：只有位置 5，j = 1个； - 中间段
s[5 : 5]是空串。
拼接：'p' + "" + "ooooo" = "pooooo"。
示例 3：s = "ppppopo"。
首字符是 'p'，前缀 'o' 个数 i = 0；末字符是 'o'，后缀 'p' 个数 j = 0。
两段都是空的，拼接结果 "" + "ppppopo" + "" 还是 "ppppopo"，与样例一致。
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 数两段长度后直接拼接 | O(n) | O(n) | 结果串本身占 O(n)，推荐 |
| 切出两段再交换 | O(n) | O(n) | 结果相同，写法稍繁琐 |
易错点总结
1. 前缀只数 'o'，后缀只数 'p'
两段数的不是同一种字符。前缀遇到 'p' 就要停，后缀遇到 'o' 就要停，
否则会多切一段、把中间内容也换掉。
2. 以为两段长度一定相等
题目只要求「尽可能多」，没有要求长度相同。"ooooop" 里两段长度就是 5 和 1。
3. 没有可交换的段时不要报错
字符串以 'p' 开头或者以 'o' 结尾时，对应那一段长度为 0，
交换后字符串不变。代码里 i = 0 或 j = 0 会自然退化成「不换」，不需要特判。
4. 切片下标不要写反
中间段是 s[i : n - j]（左闭右开），不是 s[i : n - j + 1]，
也不是 s[i : j]。写错很容易在样例上就露馅。
5. 数据量到 10^5
虽然 Python 的字符串切片本身很快，读入时仍建议用 sys.stdin.buffer.read() 一次读完。
扩展思考
- 如果前缀和后缀都数同一种字符（例如都数
'o'），两段就可能重叠，
这时要先约定「重叠时怎么切」，题目难度会上升。 - 如果要求交换后字符串的字典序最小，需要对「只换前缀」「只换后缀」「两段都换」
三种方案分别比较。 - 本题的思路（数出连续段的长度，再按长度拼接）在「翻转前缀」「删除连续段」
这类字符串模拟题里通用。