Cerinta completa

Consider a string, , of lowercase English letters where each character, (, denotes the letter at index in . We define an palindromic tuple of to be a sequence of indices in satisfying the following criteria:

  • , meaning the characters located at indices and are the same.
  • , meaning the characters located at indices and are the same.
  • , meaning that , , , and are ascending in value and are valid indices within string .

Given , find and print the number of tuples satisfying the above conditions. As this value can be quite large, print it modulo .

Function Description
Complete the function shortPalindrome in the editor below.

shortPalindrome has the following paramter(s):
– string s: a string

Returns
– int: the number of tuples, modulo

Input Format

A single string, .

Constraints

  • It is guaranteed that only contains lowercase English letters.

Sample Input 0

kkkkkkz

Sample Output 0

15

Explanation 0

The letter z will not be part of a valid tuple because you need at least two of the same character to satisfy the conditions defined above. Because all tuples consisting of four k‘s are valid, we just need to find the number of ways that we can choose four of the six k‘s. This means our answer is .

Sample Input 1

ghhggh

Sample Output 1

4

Explanation 1

The valid tuples are:

Thus, our answer is .

Sample Input 0

kkkkkkz

Sample Output 0

15

Sample Input 1

abbaab

Sample Output 1

4

Sample Input 2

akakak

Sample Output 2

2

Explanation 2

Tuples possible are

Limbajul de programare folosit: rust

Cod:

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

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

fn shortPalindrome(s: &str) -> i32 {
    let mut table_i = vec![0;26];
    let mut table_ij = vec![vec![0;26];26];
    let mut table_ijj = vec![0;26];
    let mut result = 0;
    let modulo = 1000000007;

    for ch in s.chars() {
        let i = ch as usize - 'a' as usize;

        result = (result + table_ijj[i]) % modulo;

        for j in 0..26 {
            table_ijj[j] = (table_ijj[j] + table_ij[i][j]) % modulo;
            table_ij[i][j] = (table_ij[i][j] + table_i[j]) % modulo;
        }
        
        table_i[i] += 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 = shortPalindrome(&s);

    println!("{}", result);

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

Scor obtinut: 1.0

Submission ID: 464612273

Link challenge: https://www.hackerrank.com/challenges/short-palindrome/problem

Short Palindrome