2023.6.3 单字符重复子串的最大长度-526互联

是一个思维题。

假设我们现在有一个左闭右开区间\([i, j)\)，其中的所有元素都是相同的，为a。如果现在处于位置j上的元素不是a，而整个字符串上的其他位置还有a存在，那么我们肯定可以把它们互换，使得\([i, j]\)内的所有元素都变成a，所以答案可以+1。
在1的基础之上，如果\([j + 1, k)\)上的元素也都是a，我们把位置j的元素换成a之后，两个串就会拼在一起，变成\([i, k)\)内的所有元素都是a。这种情况下，答案是\(k-i\)。不过需要考虑一个特殊情况，即j在其他位置上找a来换时，找的这个a正是\([j + 1, k)\)里的a，这种情况下，答案不应该是\(k-i\)，而是\(min(cnt['a'], k - i)\)，即字符串中a的最大数量和\(k-i\)取一个最小值。

use std::cmp::{max, min};
use std::collections::{HashMap, HashSet};

impl Solution {
    pub fn max_rep_opt1(text: String) -> i32
    {
        let str = text.as_bytes();
        let mut cnt: HashMap<u8, usize> = HashMap::new();
        str.iter().for_each(|x| {cnt.entry(*x).and_modify(|v| *v += 1).or_insert(1);});

        let (mut res, n) = (0, str.len());
        for mut i in 0..n
        {
            let mut j = i;
            while j < n && str[j] == str[i] { j += 1; }
            
            if cnt[&str[i]] > j - i && (i > 0 || j < n) { res = max(res, j - i + 1); }
            let mut k = j + 1;
            while k < n && str[k] == str[i] { k += 1; }
            
            res = max(res, min(cnt[&str[i]], k - i));
            i = j;
        }

        res as i32
    }
}

单字