leetcode
leetcode 1101 ~ 1150
单字符重复子串的最大长度

单字符重复子串的最大长度

难度:

标签:

题目描述

代码结果

运行时间: 43 ms, 内存: 17.3 MB


/*
 * Problem Statement: Given a string text, you can swap two characters once or do nothing to form substrings of repeated characters. Return the length of the longest such substring.
 * 
 * Approach using Java Stream:
 * 1. Use a stream to create groups of consecutive identical characters.
 * 2. Calculate maximum possible lengths similar to the standard approach.
 * 3. Return the maximum length found.
 */
import java.util.*;
import java.util.stream.Collectors;

public class Solution {
    public int maxRepOpt1(String text) {
        int n = text.length();
        if (n <= 1) return n;
        Map<Character, Long> countMap = text.chars().mapToObj(c -> (char)c)
            .collect(Collectors.groupingBy(c -> c, Collectors.counting()));
        List<int[]> groups = new ArrayList<>();
        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && text.charAt(j) == text.charAt(i)) j++;
            groups.add(new int[]{text.charAt(i) - 'a', j - i});
            i = j;
        }

        return groups.stream().mapToInt(group -> {
            int currentChar = group[0];
            int groupLen = group[1];
            int maxLen = groupLen;
            if (countMap.get((char)(currentChar + 'a')) > groupLen) {
                maxLen = Math.max(maxLen, groupLen + 1);
            }
            for (int k = 0; k < groups.size() - 2; k++) {
                if (groups.get(k + 1)[1] == 1 && groups.get(k + 2)[0] == currentChar) {
                    maxLen = Math.max(maxLen, groupLen + groups.get(k + 2)[1]);
                    if (countMap.get((char)(currentChar + 'a')) > groupLen + groups.get(k + 2)[1]) {
                        maxLen = Math.max(maxLen, groupLen + groups.get(k + 2)[1] + 1);
                    }
                }
            }
            return maxLen;
        }).max().orElse(0);
    }
}

解释

方法:

题解的主要思路是通过动态规划和额外的统计数组来解决问题。首先,使用一个数组 `appear_times` 来记录每个字符在文本中出现的次数。同时,使用两个数组 `max_consec` 和 `max_gap` 分别记录每个字符连续出现的最大长度和可能通过一次交换后能达到的最大长度。动态规划数组 `dp` 的每个元素包含两个值,分别表示当前位置连续的字符长度和可能的最长交换后长度。在遍历字符串时,根据当前字符是否与前一个字符相同来更新 `dp` 数组,以及对应的 `max_consec` 和 `max_gap`。最后,根据字符的出现次数,利用 `max_consec` 和 `max_gap` 计算可能的最大长度。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在代码中`dp`数组的每个元素包含两个值,其中第二个值是如何计算的,特别是在字符不连续时?
在代码中,`dp`数组的每个元素为一个元组,其中第一个值记录当前位置连续的相同字符的最大长度,而第二个值记录可能通过一次交换后能够达到的最大长度。当字符不连续时,此时`dp[i][1]`的计算需要判断当前字符与前前一个字符是否相同(即`text[i] == text[i - 2]`)。如果相同,表示通过交换`text[i - 1]`和`text[i]`之间的字符,可以将`text[i]`连到`text[i - 2]`之前形成的连续子串上,因此`dp[i][1] = dp[i - 2][0] + 1`。这种情况下,我们假设通过一次交换可以修正一个间断,从而增加连续子串的长度。如果不相同,则`dp[i][1]`重置为1,因为当前字符未能通过交换与前面的字符形成更长的连续子串。
🦆
题解中提到`可能通过一次交换后能达到的最大长度`,具体是如何确定一个字符通过交换可以增加的最大长度?
代码中通过动态规划在`dp[i][1]`中记录可能通过一次交换后能达到的最大长度。这一计算基于当前字符是否能与它前面非连续的字符形成连续串。如果当前字符与前前字符相同,并且中间只有一个不同的字符,那么可以通过交换这个不同字符,将当前字符加入到前面的连续字符串中。因此,`dp[i][1]`在这种情况下会设置为`dp[i - 2][0] + 1`。此外,代码在更新`max_gap`数组时,会检查每个字符的`dp[i][1]`值,以确定通过一次交换可能达到的最大长度。
🦆
为什么在更新`max_gap`数组时使用`dp[i][1]`的值,这里的逻辑是什么?
`max_gap`数组用于记录每个字符通过一次交换后可能达到的最大连续长度。在每次更新`dp[i][1]`时,它记录了当前字符通过一次交换后可能形成的最大连续区间。因此,每当`dp[i][1]`被计算时,代码会检查并更新`max_gap`数组中对应字符的最大值。这样,`max_gap`可以为每个字符存储通过一次优化交换后可能获得的最长连续子串长度。
🦆
代码中对于只出现一次的字符,返回的最大长度直接是`max_consec[i]`,这是否意味着对于单个字符的交换没有考虑?
确实如此,对于在字符串中只出现一次的字符,它的最大连续长度当然是1(因为它本身就是一个单独的字符),而`max_gap[i]`在此情况下也不会超过1,因为没有其他相同的字符进行交换。因此,对于只出现一次的字符,考虑交换来增加长度是没有意义的,所以最大长度直接是`max_consec[i]`,即1。这里的处理逻辑正确地反映了对于单个字符交换的不可行性。

相关问题