2022-07-21: given a string STR and a positive number k, you can divide STR into multiple substrings at will. The purpose is to find that in a certain division scheme, there are as many palindrome subs

2022-07-21： Given a string str, And a positive number k,
You can divide at will str Into multiple substrings ,
The purpose is to find in a certain partition scheme , There are as many palindromes as possible , length >=k, And there is no coincidence .
There are several palindrome substrings returned .
come from optiver.

answer 2022-07-21：

Horse drawn car algorithm + greedy .

The code to use rust To write . The code is as follows ：

use rand::Rng;
fn main() {
    
    let n: i32 = 20;
    let r = 3;
    let test_time: i32 = 50000;
    println!(" Beginning of the test ");
    for i in 0..test_time {
    
        let str = random_string(n, r);
        let k = rand::thread_rng().gen_range(0, str.len() as i32) + 1;
        let ans1 = max1(&str, k);
        let ans2 = max2(&str, k);
        if ans1 != ans2 {
    
            println!("i = {}", i);
            println!("str = {}", str);
            println!("k = {}", k);
            println!("ans1 = {}", ans1);
            println!("ans2 = {}", ans2);
            println!(" Something went wrong !");
            break;
        }
    }
    println!(" End of test ");
}
//  Violent attempts 
//  In order to test 
//  It can be changed into dynamic programming , But not the best solution 
fn max1(s: &str, k: i32) -> i32 {
    
    if s.len() == 0 {
    
        return 0;
    }
    let mut str = s.as_bytes().to_vec();
    return process1(&mut str, 0, k);
}

fn process1(str: &mut Vec<u8>, index: i32, k: i32) -> i32 {
    
    if str.len() as i32 - index < k {
    
        return 0;
    }
    let mut ans = process1(str, index + 1, k);
    for i in index + k - 1..str.len() as i32 {
    
        if is_palindrome(str, index, i) {
    
            ans = get_max(ans, 1 + process1(str, i + 1, k));
        }
    }
    return ans;
}

fn is_palindrome(str: &mut Vec<u8>, mut ll: i32, mut rr: i32) -> bool {
    
    while ll < rr {
    
        if str[ll as usize] != str[rr as usize] {
    
            return false;
        }
        ll += 1;
        rr -= 1;
    }
    return true;
}

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

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

//  Optimal solution 
//  Time complexity O(N)
fn max2(s: &str, k: i32) -> i32 {
    
    if s.len() == 0 {
    
        return 0;
    }
    let mut str = manacher_string(s);
    let mut p = vec![];
    for _ in 0..str.len() as i32 {
    
        p.push(0);
    }
    let mut ans = 0;
    let mut next = 0;
    // k == 5  Palindrome string length should be  >= 5
    // next == 0
    // 0.... 8  First block ！
    // next -> 9
    // 9.....17  Second pieces ！
    // next -> 18
    // 18....23  Third pieces 
    // next All the way to the end !
    next = manacher_find(&mut str, &mut p, next, k);
    while next != -1 {
    
        next = if str[next as usize] == ('#' as u8) {
    
            next
        } else {
    
            next + 1
        };
        ans += 1;
        next = manacher_find(&mut str, &mut p, next, k);
    }
    return ans;
}

fn manacher_string(s: &str) -> Vec<u8> {
    
    let str = s.as_bytes().to_vec();
    let mut ans: Vec<u8> = vec![];
    for _ in 0..str.len() as i32 * 2 + 1 {
    
        ans.push(0);
    }
    let mut index: i32 = 0;
    for i in 0..ans.len() as i32 {
    
        if (i & 1) == 0 {
    
            ans[i as usize] = '#' as u8;
        } else {
    
            ans[i as usize] = str[index as usize];
            index += 1;
        }
    }
    return ans;
}

// s[l...] The string is only in this range , And s[l] It must be '#'
//  From the subscript l Start , Not before , Once there is a certain central palindrome radius >k, Immediately return to the right boundary 
fn manacher_find(s: &mut Vec<u8>, p: &mut Vec<i32>, l: i32, k: i32) -> i32 {
    
    let mut c = l - 1;
    let mut r = l - 1;
    let n = s.len() as i32;
    for i in l..s.len() as i32 {
    
        p[i as usize] = if r > i {
    
            get_min(p[(2 * c - i) as usize], r - i)
        } else {
    
            1
        };
        while i + p[i as usize] < n
            && i - p[i as usize] > l - 1
            && s[(i + p[i as usize]) as usize] == s[(i - p[i as usize]) as usize]
        {
    
            p[i as usize] += 1;
            if p[i as usize] > k {
    
                return i + k;
            }
        }
        if i + p[i as usize] > r {
    
            r = i + p[i as usize];
            c = i;
        }
    }
    return -1;
}

//  In order to test 
fn random_string(n: i32, r: i32) -> String {
    
    let mut ans: String = String::from("");
    let ans_len = rand::thread_rng().gen_range(1, n);
    for _ in 0..ans_len {
    
        ans.push((rand::thread_rng().gen_range(0, r) + 'a' as i32) as u8 as char);
    }
    return ans;
}

The results are as follows ：

Zuo Shen java Code