2022-11-01：給定一個隻由小寫字母和數字字元組成的字元串str

2022-11-01：給定一個隻由小寫字母和數字字元組成的字元串str。

要求子串必須隻含有一個小寫字母，數字字元數量随意。

求這樣的子串最大長度是多少？

答案2022-11-01：

經典的滑動視窗問題。

時間複雜度：O(N)。

空間複雜度：O(1)。

代碼用rust編寫。代碼如下：

use rand::Rng;
fn main() {
    let nn: i32 = 100;
    let test_time: i32 = 10000;
    println!("測試開始");
    for _ in 0..test_time {
        let n = rand::thread_rng().gen_range(0, nn) + 1;
        let str = random_string(n);
        let ans1 = right(&str);
        let ans2 = zuo(&str);
        if ans1 != ans2 {
            println!("ans1 = {:?}", ans1);
            println!("ans2 = {:?}", ans2);
            println!("出錯了!");
            break;
        }
    }
    println!("測試結束");
}


// 一個絕對正确的暴力方法
fn right(s: &str) -> i32 {
    let str = s.as_bytes();
    let mut ans = 0;
    for i in 0..str.len() as i32 {
        for j in i..str.len() as i32 {
            if check(str, i, j) {
                ans = get_max(ans, j - i + 1);
            }
        }
    }
    return ans;
}


fn check(str: &[u8], l: i32, r: i32) -> bool {
    let mut letter_number = 0;
    for i in l..=r {
        if str[i as usize] >= 'a' as u8 && str[i as usize] <= 'z' as u8 {
            letter_number += 1;
        }
    }
    return letter_number == 1;
}


fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}


// 用視窗
// 時間複雜度O(N)
fn zuo(s: &str) -> i32 {
    let str = s.as_bytes();
    let n = str.len() as i32;
    // 視窗内有幾個小寫字母了
    let mut letters = 0;
    // 視窗的右邊界
    // [left, right)
    let mut right = 0;
    let mut ans = 0;
    // for枚舉了每一個視窗的開始位置，0... 1...... 2.....
    for left in 0..n {
        while right < n {
            // right不能越界，一旦越界不用再往右了
            if letters == 1 && str[right as usize] >= 'a' as u8 && str[right as usize] <= 'z' as u8
            {
                break;
            }
            // letters == 0 str[right]是數字
            if str[right as usize] >= 'a' as u8 && str[right as usize] <= 'z' as u8 {
                letters += 1;
            }
            right += 1;
        }
        // [left.....right)
        // [left.....right-1]
        if letters == 1 {
            ans = get_max(ans, right - left);
        }
        if str[left as usize] >= 'a' as u8 && str[left as usize] <= 'z' as u8 {
            letters -= 1;
        }
    }
    return ans;
}


// 為了測試
const CHARS: [char; 36] = [
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i',
    'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
];


// 為了測試
fn random_string(n: i32) -> String {
    let mut ans = String::from("");
    for _i in 0..n {
        ans.push(CHARS[rand::thread_rng().gen_range(0, 36)]);
    }
    return ans;
}

           

執行結果如下：

***

[左神java代碼](https://github.com/algorithmzuo/weekly-problems/blob/main/src/class_2022_08_1_week/Code05_LongestOneLetterManyNumberString.java)