小欧的前后缀交换

[题目链接](https://www.nowcoder.com/practice/79e1a3eb38cd4473b490172619326be2)

思路

本题给定一个仅由 'o' 和 'p' 组成的字符串，要求将前缀中尽可能多的连续 'o' 和后缀中尽可能多的连续 'p' 交换一次。

分析

我们可以把字符串分成三段：

$ $s = \underbrace{ooo\cdots o}_{\text{prefix\_o}} + \underbrace{\text{middle}}_{\text{中间部分}} + \underbrace{ppp\cdots p}_{\text{suffix\_p}}$ $

prefix_o：从头开始最长的连续 'o' 段
suffix_p：从尾部开始最长的连续 'p' 段
middle：夹在中间的部分

交换操作就是把 prefix_o 和 suffix_p 互换位置，结果为：

$ $\text{result} = \text{suffix\_p} + \text{middle} + \text{prefix\_o}$ $

举例

以样例 ooppoopp 为例：

部分	内容
prefix_o	`oo`（前 2 个字符都是 `'o'`）
middle	`ppoo`（下标 2~5）
suffix_p	`pp`（最后 2 个字符都是 `'p'`）

交换后：pp + ppoo + oo = ppppoooo。

再看 ppppopo：前缀没有连续的 'o'（第一个字符就是 'p'），后缀也没有连续的 'p'（最后一个字符是 'o'），两段都为空，交换后字符串不变。

实现

从左往右扫，统计 prefix_o 的长度
从右往左扫，统计 suffix_p 的长度
拼接：suffix_p + middle + prefix_o

时间和空间都是线性的，完全满足 $n \le 100000$ 的约束。

代码

C++
Java

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();

    // 统计前缀连续 'o' 的长度
    int prefixLen = 0;
    while (prefixLen < n && s[prefixLen] == 'o') prefixLen++;

    // 统计后缀连续 'p' 的长度
    int suffixLen = 0;
    while (suffixLen < n && s[n - 1 - suffixLen] == 'p') suffixLen++;

    // 拼接：suffix_p + middle + prefix_o
    cout << s.substr(n - suffixLen, suffixLen)
            + s.substr(prefixLen, n - prefixLen - suffixLen)
            + s.substr(0, prefixLen) << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int n = s.length();

        // 统计前缀连续 'o' 的长度
        int prefixLen = 0;
        while (prefixLen < n && s.charAt(prefixLen) == 'o') prefixLen++;

        // 统计后缀连续 'p' 的长度
        int suffixLen = 0;
        while (suffixLen < n && s.charAt(n - 1 - suffixLen) == 'p') suffixLen++;

        // 拼接：suffix_p + middle + prefix_o
        String result = s.substring(n - suffixLen, n)
                       + s.substring(prefixLen, n - suffixLen)
                       + s.substring(0, prefixLen);

        System.out.println(result);
    }
}

复杂度分析

时间复杂度： $O(n)$ ，扫描两次加一次字符串拼接。
空间复杂度： $O(n)$ ，存储结果字符串。