Cerinta completa

Shaka and his brother have created a boring game which is played like this:

They take a word composed of lowercase English letters and try to get the maximum possible score by building exactly 2 palindromic subsequences. The score obtained is the product of the length of these 2 subsequences.

Let’s say and are two subsequences from the initial string. If & are the smallest and the largest positions (from the initial word) respectively in ; and & are the smallest and the largest positions (from the initial word) respectively in , then the following statements hold true:
,
, &
.
i.e., the positions of the subsequences should not cross over each other.

Hence the score obtained is the product of lengths of subsequences & . Such subsequences can be numerous for a larger initial word, and hence it becomes harder to find out the maximum possible score. Can you help Shaka and his brother find this out?

Input Format

Input contains a word composed of lowercase English letters in a single line.

Constraints


each character will be a lower case english alphabet.

Output Format

Output the maximum score the boys can get from .

Sample Input

eeegeeksforskeeggeeks

Sample Output

50

Explanation

A possible optimal solution is eee-g-ee-ksfor-skeeggeeks being eeeee the one subsequence and skeeggeeks the other one. We can also select eegee in place of eeeee, as both have the same length.

Limbajul de programare folosit: rust

Cod:

use std::env;
use std::fs::File;
use std::io::{self, BufRead, Write};

/*
 * Complete the 'playWithWords' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts STRING s as parameter.
 */

fn playWithWords(s: &str) -> i32 {
    let n = s.len();
    let seq = s.as_bytes();
    let mut dp: Vec<Vec<i32>> = vec![vec![0; n]; n];

    for i in 0..n {
        dp[i][i] = 1;
    }

    for length in 2..=n {
        for i in 0..=(n - length) {
            let j = i + length - 1;

            if seq[i] == seq[j] {
                if length == 2 {
                    dp[i][j] = 2;
                } else {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                }
            } else {
                dp[i][j] = dp[i][j - 1].max(dp[i + 1][j]);
            }
        }
    }

    let mut result = 0;

    for i in 1..n {
        if result < dp[0][i - 1] * dp[i][n - 1] {
            result = dp[0][i - 1] * dp[i][n - 1];
        }
    }

    result
}

fn main() {
    let stdin = io::stdin();
    let mut stdin_iterator = stdin.lock().lines();

    // let mut fptr = File::create(env::var("OUTPUT_PATH").unwrap()).unwrap();

    let s = stdin_iterator.next().unwrap().unwrap();

    let result = playWithWords(&s);

    println!("{}", result);
    // writeln!(&mut fptr, "{}", result).ok();
}

Scor obtinut: 1.0

Submission ID: 464612742

Link challenge: https://www.hackerrank.com/challenges/strplay/problem

Play with words