题解

题面描述

给定一个长度为 $n$ 的字符串数组，每个字符串由若干个小写字母组成。定义一个字符串数组的权值为最长连续相同字符串的区间长度。现在小红想知道，若恰好删除一段连续非空区间，剩下的字符串数组的权值最大是多少。

思路

这道题的核心思路是，对于每个字符串，首先判断是否每个字符都相同。如果是，直接输出字符串长度减一。如果不是，则通过遍历字符串，记录每个字符连续出现的区间长度。接着，使用哈希表保存每个字符的连续区间信息，排序后选取最大的两个区间长度来合并，从而得到删除某段区间后的最大权值。最后输出每个字符串的最大权值。

1. 每个字符的连续区间处理：

   • 对每个字符串，首先检查是否每个字符都相同。如果是，删除一个字符后，权值就是字符串的长度减一。

2. 分段计数：

   • 如果字符串中的字符不完全相同，我们将字符串划分为多个连续相同字符的区间。例如，对于字符串 "aabbbaa"，可以划分为三个区间："aa", "bbb", "aa"。

3. 合并前后区间：

   • 对于每个字符的所有区间，检查是否可以通过删除某段区间来合并前后相同字符的区间，从而得到更大的连续区间。

4. 优化：

   • 通过哈希表存储每个字符的所有区间长度，并对每个字符的区间按从大到小的顺序进行排序。然后选择合并两个最大的区间。

C++

#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;  // 输入字符串的个数
    int max_length = 0;  // 存储最终的最大长度

    while (n--) {
        string s;
        cin >> s;  // 输入一个字符串

        // 如果字符串中每个字符都相同，那么答案就是字符串的长度减去1
        if (s.size() == count(s.begin(), s.end(), s[0])) {
            max_length = max(max_length, (int)s.size() - 1);
            continue;  // 跳过当前字符串，进入下一个字符串
        }

        int current_len = 0;  // 当前字符段的长度
        unordered_map<char, vector<int>> char_segments;  // 用于存储每个字符出现的连续段的长度

        // 遍历字符串中的每个字符
        for (int i = 0; i < s.size(); ++i) {
            if (i == 0 || s[i] == s[i - 1]) {  // 如果当前字符与前一个字符相同，增加当前字符段长度
                current_len++;
            } else {
                // 如果字符段结束，保存字符段长度
                char_segments[s[i - 1]].push_back(current_len);
                current_len = 1;  // 重置当前字符段长度
            }
        }

        // 处理字符串的最后一段
        char_segments[s[s.size() - 1]].push_back(current_len);

        // 对每个字符的连续段进行处理
        for (auto& pair : char_segments) {
            sort(pair.second.rbegin(), pair.second.rend());  // 按长度从大到小排序
            if (pair.second.size() == 1) {
                // 如果只有一个连续段，取它的长度
                max_length = max(max_length, pair.second[0]);
            } else {
                // 如果有多个连续段，取前两个段的和
                max_length = max(max_length, pair.second[0] + pair.second[1]);
            }
        }
    }

    cout << max_length << endl;  // 输出最终结果
    return 0;
}

Python

def main():
    n = int(input())  # 输入字符串的个数
    max_length = 0  # 存储最终的最大长度

    for _ in range(n):
        s = input()  # 输入一个字符串

        # 如果字符串中每个字符都相同，那么答案就是字符串的长度减去1
        if len(s) == s.count(s[0]):
            max_length = max(max_length, len(s) - 1)
            continue  # 跳过当前字符串，进入下一个字符串

        current_len = 0  # 当前字符段的长度
        char_segments = {}  # 用于存储每个字符出现的连续段的长度

        # 遍历字符串中的每个字符
        for i in range(len(s)):
            if i == 0 or s[i] == s[i - 1]:  # 如果当前字符与前一个字符相同，增加当前字符段长度
                current_len += 1
            else:
                # 如果字符段结束，保存字符段长度
                if s[i - 1] not in char_segments:
                    char_segments[s[i - 1]] = []
                char_segments[s[i - 1]].append(current_len)
                current_len = 1  # 重置当前字符段长度

        # 处理字符串的最后一段
        if s[-1] not in char_segments:
            char_segments[s[-1]] = []
        char_segments[s[-1]].append(current_len)

        # 对每个字符的连续段进行处理
        for lengths in char_segments.values():
            lengths.sort(reverse=True)  # 按长度从大到小排序
            if len(lengths) == 1:
                # 如果只有一个连续段，取它的长度
                max_length = max(max_length, lengths[0])
            else:
                # 如果有多个连续段，取前两个段的和
                max_length = max(max_length, lengths[0] + lengths[1])

    print(max_length)  # 输出最终结果

if __name__ == "__main__":
    main()

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  // 输入字符串的个数
        int maxLength = 0;  // 存储最终的最大长度

        while (n-- > 0) {
            String s = scanner.next();  // 输入一个字符串

            // 如果字符串中每个字符都相同，那么答案就是字符串的长度减去1
            if (s.length() == countChar(s, s.charAt(0))) {
                maxLength = Math.max(maxLength, s.length() - 1);
                continue;  // 跳过当前字符串，进入下一个字符串
            }

            int currentLen = 0;  // 当前字符段的长度
            Map<Character, List<Integer>> charSegments = new HashMap<>();  // 用于存储每个字符出现的连续段的长度

            // 遍历字符串中的每个字符
            for (int i = 0; i < s.length(); ++i) {
                if (i == 0 || s.charAt(i) == s.charAt(i - 1)) {  // 如果当前字符与前一个字符相同，增加当前字符段长度
                    currentLen++;
                } else {
                    // 如果字符段结束，保存字符段长度
                    charSegments.putIfAbsent(s.charAt(i - 1), new ArrayList<>());
                    charSegments.get(s.charAt(i - 1)).add(currentLen);
                    currentLen = 1;  // 重置当前字符段长度
                }
            }

            // 处理字符串的最后一段
            charSegments.putIfAbsent(s.charAt(s.length() - 1), new ArrayList<>());
            charSegments.get(s.charAt(s.length() - 1)).add(currentLen);

            // 对每个字符的连续段进行处理
            for (Map.Entry<Character, List<Integer>> entry : charSegments.entrySet()) {
                List<Integer> segments = entry.getValue();
                segments.sort(Comparator.reverseOrder());  // 按长度从大到小排序
                if (segments.size() == 1) {
                    // 如果只有一个连续段，取它的长度
                    maxLength = Math.max(maxLength, segments.get(0));
                } else {
                    // 如果有多个连续段，取前两个段的和
                    maxLength = Math.max(maxLength, segments.get(0) + segments.get(1));
                }
            }
        }

        System.out.println(maxLength);  // 输出最终结果
        scanner.close();
    }

    // 统计某个字符在字符串中出现的次数
    private static int countChar(String s, char c) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == c) {
                count++;
            }
        }
        return count;
    }
}

题目内容

小红拿到一个长度为$n$的字符串数组，每个字符串由若干个小写字母组成。

定义一个字符串数组的权值为最长连续相同字符串的区间长度。

小红想知道，若恰好删除一段连续非空区间，剩下的字符串数组的权值最大是多少。

输入描述

第一行一个整数$n(2 ≤n≤10^5)$，表示字符串数组的长度。

接下来$n$ 行，每行一个字符串，保证仅由小写字母组成。

保证所有字符串的长度之和不超过$10^6$。

输出描述

一个整数，表示删除一段连续非空区间后，剩下的字符串数组的权值最大是多少。

样例1

输入

3
aab
qwq
aab

输出

2