Question

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

English Version

题目描述

如果字符串中的所有字符都相同，那么这个字符串是单字符重复的字符串。

给你一个字符串 text，你只能交换其中两个字符一次或者什么都不做，然后得到一些单字符重复的子串。返回其中最长的子串的长度。

 

示例 1：

输入：text = "ababa"
输出：3

示例 2：

输入：text = "aaabaaa"
输出：6

示例 3：

输入：text = "aaabbaaa"
输出：4

示例 4：

输入：text = "aaaaa"
输出：5

示例 5：

输入：text = "abcdef"
输出：1

 

提示：

• 1 <= text.length <= 20000
• text 仅由小写英文字母组成。

解法

方法一：双指针

我们先用哈希表或数组 $cnt$ 统计字符串 $text$ 中每个字符出现的次数。

接下来，我们定义一个指针 $i$，初始时 $i = 0$。每一次，我们将指针 $j$ 指向 $i$，并不断地向右移动 $j$，直到 $j$ 指向的字符与 $i$ 指向的字符不同，此时我们得到了一个长度为 $l = j - i$ 的子串 $text[i..j-1]$，其中所有字符都相同。

然后我们跳过指针 $j$ 指向的字符，用指针 $k$ 继续向右移动，直到 $k$ 指向的字符与 $i$ 指向的字符不同，此时我们得到了一个长度为 $r = k - j - 1$ 的子串 $text[j+1..k-1]$，其中所有字符都相同。那么我们最多通过一次交换操作，可以得到的最长单字符重复子串的长度为 $\min(l + r + 1, cnt[text[i]])$。接下来，我们将指针 $i$ 移动到 $j$，继续寻找下一个子串。我们取所有满足条件的子串的最大长度即可。

时间复杂度为 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 为字符串的长度；而 $C$ 为字符集的大小，本题中 $C = 26$。

class Solution:
  def maxRepOpt1(self, text: str) -> int:
    cnt = Counter(text)
    n = len(text)
    ans = i = 0
    while i < n:
      j = i
      while j < n and text[j] == text[i]:
        j += 1
      l = j - i
      k = j + 1
      while k < n and text[k] == text[i]:
        k += 1
      r = k - j - 1
      ans = max(ans, min(l + r + 1, cnt[text[i]]))
      i = j
    return ans

class Solution {
  public int maxRepOpt1(String text) {
    int[] cnt = new int[26];
    int n = text.length();
    for (int i = 0; i < n; ++i) {
      ++cnt[text.charAt(i) - 'a'];
    }
    int ans = 0, i = 0;
    while (i < n) {
      int j = i;
      while (j < n && text.charAt(j) == text.charAt(i)) {
        ++j;
      }
      int l = j - i;
      int k = j + 1;
      while (k < n && text.charAt(k) == text.charAt(i)) {
        ++k;
      }
      int r = k - j - 1;
      ans = Math.max(ans, Math.min(l + r + 1, cnt[text.charAt(i) - 'a']));
      i = j;
    }
    return ans;
  }
}

class Solution {
public:
  int maxRepOpt1(string text) {
    int cnt[26] = {0};
    for (char& c : text) {
      ++cnt[c - 'a'];
    }
    int n = text.size();
    int ans = 0, i = 0;
    while (i < n) {
      int j = i;
      while (j < n && text[j] == text[i]) {
        ++j;
      }
      int l = j - i;
      int k = j + 1;
      while (k < n && text[k] == text[i]) {
        ++k;
      }
      int r = k - j - 1;
      ans = max(ans, min(l + r + 1, cnt[text[i] - 'a']));
      i = j;
    }
    return ans;
  }
};

func maxRepOpt1(text string) (ans int) {
  cnt := [26]int{}
  for _, c := range text {
    cnt[c-'a']++
  }
  n := len(text)
  for i, j := 0, 0; i < n; i = j {
    j = i
    for j < n && text[j] == text[i] {
      j++
    }
    l := j - i
    k := j + 1
    for k < n && text[k] == text[i] {
      k++
    }
    r := k - j - 1
    ans = max(ans, min(l+r+1, cnt[text[i]-'a']))
  }
  return
}

function maxRepOpt1(text: string): number {
  const idx = (c: string) => c.charCodeAt(0) - 'a'.charCodeAt(0);
  const cnt: number[] = new Array(26).fill(0);
  for (const c of text) {
    cnt[idx(c)]++;
  }
  let ans = 0;
  let i = 0;
  const n = text.length;
  while (i < n) {
    let j = i;
    while (j < n && text[j] === text[i]) {
      ++j;
    }
    const l = j - i;
    let k = j + 1;
    while (k < n && text[k] === text[i]) {
      ++k;
    }
    const r = k - j - 1;
    ans = Math.max(ans, Math.min(cnt[idx(text[i])], l + r + 1));
    i = j;
  }
  return ans;
}