RUST GYM Google KickStart Year 2021 Round 1 k goodness string Rust Solution

k goodness string

Problem

Charles defines the goodness score of a string as the number of indices $i$ such that $\mathbf{S}_i\ne\mathbf{S}_{\mathbf{N}-i+1}$ where $1 \le i \le \mathbf{N}/2$ ( $1$ -indexed). For example, the string CABABC has a goodness score of $2$ since $\mathbf{S}_2 \ne \mathbf{S}_5$ and $\mathbf{S}_3 \ne \mathbf{S}_4$ .

Charles gave Ada a string $\mathbf{S}$ of length $\mathbf{N}$ , consisting of uppercase letters and asked her to convert it into a string with a goodness score of $\mathbf{K}$ . In one operation, Ada can change any character in the string to any uppercase letter. Could you help Ada find the minimum number of operations required to transform the given string into a string with goodness score equal to $\mathbf{K}$ ?

Input

The first line of the input gives the number of test cases, $\mathbf{T}$ . $\mathbf{T}$ test cases follow.

The first line of each test case contains two integers $\mathbf{N}$ and $\mathbf{K}$ . The second line of each test case contains a string $\mathbf{S}$ of length $\mathbf{N}$ , consisting of uppercase letters.

Output

For each test case, output one line containing Case # $x$ : $y$ , where $x$ is the test case number (starting from 1) and $y$ is the minimum number of operations required to transform the given string $\mathbf{S}$ into a string with goodness score equal to $\mathbf{K}$ .

Limits

Memory limit: 1 GB.
$1 \le \mathbf{T} \le 100$ .
$0 \le \mathbf{K} \le \mathbf{N}/2$ .

Test Set 1

Time limit: 20 seconds.
$1 \le \mathbf{N} \le 100$ .

Test Set 2

Time limit: 40 seconds.
$1 \le \mathbf{N} \le 2 \times 10^5$ for at most $10$ test cases.
For the remaining cases, $1 \le \mathbf{N} \le 100$ .

In Sample Case #1, the given string already has a goodness score of $1$ . Therefore the minimum number of operations required is $0$ .

In Sample Case #2, one option is to change the character at index $1$ to B in order to have a goodness score of $2$ . Therefore, the minimum number of operations required is $1$ .

Sample Input & Output

2
5 1
ABCAA
4 2
ABAA

Case #1: 0
Case #2: 1

Rust Solution

use rustgym_util::*;
use std::fmt::Write;
use std::io::*;

fn solve(case_no: usize, reader: &mut impl BufRead, writer: &mut impl Write) {
    let args: Vec<usize> = reader.parse_vec();
    let n = args[0];
    let k = args[1] as i32;
    let s: Vec<char> = reader.collect_string().chars().collect();
    let mut g = 0;
    for i in 0..n / 2 {
        if s[i] != s[n - 1 - i] {
            g += 1;
        }
    }
    let res = (g - k).abs();
    writeln!(writer, "Case #{}: {}", case_no, res).unwrap();
}

google_test_gen!(test, "input.txt", "output.txt");

Analysis

As per the given definition of operation, Ada can only change the goodness score by one in a single move. Therefore to get a string with the required goodness score in the minimum number of operations Ada can either increase or decrease the goodness score by one in each step. Let us assume there are $X$ indices( $\le \mathbf{N}/2$ ( $1$ -indexed)) $i$ in the given string $\mathbf{S}$ such that $\mathbf{S}_i \neq \mathbf{S}_{\mathbf{N}-i+1}$ . We have 3 cases now.

Case 1: $X = \mathbf{K}$ ,
In this case, Ada already has the string which has a goodness score of $\mathbf{K}$ . Therefore number of operations required is $0$ .
Case 2: $X > \mathbf{K}$ ,
In this case, Ada can change $(X-\mathbf{K})$ letters at indices $i$ ( $1 <= i <= \mathbf{N}/2$ ( $1$ -indexed)) that satisfy $\mathbf{S}_i \neq \mathbf{S}_{\mathbf{N}-i+1}$ to the letter at $\mathbf{S}_{\mathbf{N}-i+1}$ . Then she will have a string with a goodness score of $\mathbf{K}$ . Therefore the minimum number of operations is $(X-\mathbf{K})$ .
Case 3: $X < \mathbf{K}$ ,
In this case, Ada can change $(\mathbf{K}-X)$ letters at indices $i$ ( $1 <= i <= \mathbf{N}/2$ ( $1$ -indexed)) that satisfy $\mathbf{S}_i = \mathbf{S}_{\mathbf{N}-i+1}$ to any other uppercase letter other than the one at $\mathbf{S}_{\mathbf{N}-i+1}$ . As a result, she will have a string with a goodness score of $\mathbf{K}$ . Therefore the minimum number of operations is $(\mathbf{K}-X)$ .

All the above described operations can be done in $O(\mathbf{N})$ complexity. Therefore the overall complexity is $O(\mathbf{N})$ .

Sample Code (C++)


int kGoodnessString(string s, int k) {
  int minOperations = 0, x = 0;
  for(int i = 0; i < s.size() / 2; i++) {
     if(s[i] != s[s.size() - i - 1]) {
         x++;
     }
  }

if(x == k) {
minOperations = 0;
}
else if(x > k) {
minOperations = x - k;
}
else {
minOperations = k - x;
}
return minOperations;
}

Having problems with this solution? Click here to submit an issue on github.