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

Categories:

题目描述
思路分析
1. 解法一：枚举字符 + 滑动窗口（推荐）
相似题目

题目描述

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

思路分析

解法一：枚举字符 + 滑动窗口（推荐）

核心思路：

统计每个字符的总出现次数 total[c]。

对每个字符 c，用滑动窗口维护最多包含一个非 c 字符的区间。

窗口长度不超过 total[c]，更新全局最大值。

复杂度分析：

时间复杂度：O(26 * n)，其中 n 表示字符串长度。

空间复杂度：O(1)，仅使用常数级计数数组。

class Solution {
    public int maxRepOpt1(String text) {
        int n = text.length();
        int[] total = new int[26];
        for (int i = 0; i < n; i++) {
            total[text.charAt(i) - 'a']++;
        }

        int ans = 0;
        for (int c = 0; c < 26; c++) {
            if (total[c] == 0) {
                continue;
            }

            int left = 0;
            int diff = 0;

            for (int right = 0; right < n; right++) {
                if (text.charAt(right) - 'a' != c) {
                    diff++;
                }

                while (diff > 1) {
                    if (text.charAt(left) - 'a' != c) {
                        diff--;
                    }
                    left++;
                }

                int window = right - left + 1;
                if (window > total[c]) {
                    window = total[c];
                }
                ans = Math.max(ans, window);
            }
        }

        return ans;
    }
}

func maxRepOpt1(text string) int {
	n := len(text)
	total := make([]int, 26)
	for i := 0; i < n; i++ {
		total[text[i]-'a']++
	}

	ans := 0
	for c := 0; c < 26; c++ {
		if total[c] == 0 {
			continue
		}

		left := 0
		diff := 0

		for right := 0; right < n; right++ {
			if int(text[right]-'a') != c {
				diff++
			}

			for diff > 1 {
				if int(text[left]-'a') != c {
					diff--
				}
				left++
			}

			window := right - left + 1
			if window > total[c] {
				window = total[c]
			}
			if window > ans {
				ans = window
			}
		}
	}

	return ans
}

相似题目

题目	难度	考察点
424. 替换后的最长重复字符	中等	滑动窗口
1004. 最大连续1的个数 III	中等	滑动窗口
487. 最大连续1的个数 II	中等	滑动窗口
159. 至多包含两个不同字符的最长子串	中等	滑动窗口
340. 至多包含 K 个不同字符的最长子串	困难	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/69013885