Transform the String ( DSA INTERVIEW PREPARATION PROBLEMS AND SOLUTIONS ) ~ Multiplex Coder

Problem

You are given a string $S$ which denotes a padlock consisting of lower case English letters. You are also given a string $F$ consisting of set of favorite lower case English letters. You are allowed to perform several operations on the padlock. In each operation, you can change one letter of the string to the one following it or preceding it in the alphabetical order. For example: for the letter c, you are allowed to change it to either b or d in an operation. The letters can be considered in a cyclic order, i.e., the preceding letter for letter a would be letter z. Similarly, the following letter for letter z would be letter a.

Your aim is to find the minimum number of operations that are required such that each letter in string $S$ after applying the operations, is present in string $F$ .

Input

The first line of the input gives the number of test cases, $T$ . $T$ test cases follow.

Each test case consists of two lines.
The first line of each test case contains the string $S$ .
The second line of each test case contains the string $F$ .

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 that are required such that each letter in string $S$ after applying the operations, is one of the characters in string $F$ .

Limits

Memory limit: 1 GB.
$1 \leq T \leq 100$ .
$1 \leq$ the length of $S \leq 10^{5}$ .
$S$ only consists of lower case English letters.
$F$ only consists of distinct lower case English letters.
The letters in string $F$ are lexicographically sorted.

Test Set 1

Time limit: 20 seconds.
The length of $F = 1$ .

Test Set 2

Time limit: 40 seconds.
$1 \leq$ the length of $F \leq 26$ .

Sample

Note: there are additional samples that are not run on submissions down below.

Sample Input

2
abcd
a
pppp
p

Sample Output

Case #1: 6
Case #2: 0

In Sample Case #1, all the letters in string $S$ should be converted to letter a. We can keep on changing the letters to its preceding letter till we reach the letter a. We do not need to change the first letter as it is already a. The second letter needs $1$ operation to change it to a. The third letter needs $2$ operations to change it to a. The fourth letter needs $3$ operation to change it to a. Hence, we need a total of $6$ operations to change string $S$ such that all letters are changed to a.

In Sample Case #2, string $S$ already contains only the favorite letter from string $F$ . Hence, we do not require any more operations.

Additional Sample - Test Set 2

The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.

Sample Input

3
pqrst
ou
abd
abd
aaaaaaaaaaaaaaab
aceg

Sample Output

Case #1: 9
Case #2: 0
Case #3: 1

In Sample Case #1, all the letters in string $S$ should be converted to either the letter o or the letter u. For the first and second letters it is optimal to change them to preceding letters till they are changed to letter o. The first letter would take $1$ operation to change to letter o. The second letter would take $2$ operations to change to letter o. For fourth and fifth letters it is optimal to change them to following letters till they are changed to letter u. The fourth letter would take $2$ operations to change to letter u. The fifth letter would take $1$ operation to change to letter u. We can change the third letter to either o or u as both of them would require $3$ operations. Hence, we need a total of $9$ operations to change string $S$ such that all letters are changed to either o or u.

In Sample Case #2, string $S$ already contains only the favorite letters from string $F$ . Hence, we do not require any more operations.

In Sample Case #3, we only need to change the last letter b to either a or c. Thus, we only need $1$ operation.

Code:

#include "bits/stdc++.h"

#include "ext/pb_ds/assoc_container.hpp"

#include "ext/pb_ds/tree_policy.hpp"

using namespace std;

using namespace __gnu_pbds;

template<class T>

using ordered_set = tree<T, null_type,less<T>, rb_tree_tag, tree_order_statistics_node_update> ;

template<class key, class value, class cmp = std::less<key>>

using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

// find_by_order(k) returns iterator to kth element starting from 0;

// order_of_key(k) returns count of elements strictly smaller than k;

template<class T>

using min_heap = priority_queue<T,vector<T>,greater<T> >;

/*/---------------------------IO(Debugging)----------------------/*/

template<class T> istream& operator >> (istream &is, vector<T>& V) {

for(auto &e : V)

is >> e;

return is;

}

template<class T, size_t N> istream& operator >> (istream &is, array<T, N>& V) {

for(auto &e : V)

is >> e;

return is;

}

#ifdef __SIZEOF_INT128__

ostream& operator << (ostream &os, __int128 const& value){

static char buffer[64];

int index = 0;

__uint128_t T = (value < 0) ? (-(value + 1)) + __uint128_t(1) : value;

if (value < 0)

os << '-';

else if (T == 0)

return os << '0';

for(; T > 0; ++index){

buffer[index] = static_cast<char>('0' + (T % 10));

T /= 10;

}

while(index > 0)

os << buffer[--index];

return os;

}

istream& operator >> (istream& is, __int128& T){

static char buffer[64];

is >> buffer;

size_t len = strlen(buffer), index = 0;

T = 0; int mul = 1;

if (buffer[index] == '-')

++index, mul *= -1;

for(; index < len; ++index)

T = T * 10 + static_cast<int>(buffer[index] - '0');

T *= mul;

return is;

}

#endif

template<typename CharT, typename Traits, typename T>

ostream& _containerprint(std::basic_ostream<CharT, Traits> &out, T const &val) {

return (out << val << " ");

}

template<typename CharT, typename Traits, typename T1, typename T2>

ostream& _containerprint(std::basic_ostream<CharT, Traits> &out, pair<T1, T2> const &val) {

return (out << "(" << val.first << "," << val.second << ") ");

}

template<typename CharT, typename Traits, template<typename, typename...> class TT, typename... Args>

ostream& operator << (std::basic_ostream<CharT, Traits> &out, TT<Args...> const &cont) {

out << "[ ";

for(auto&& elem : cont) _containerprint(out, elem);

return (out << "]");

}

template<class L, class R> ostream& operator << (ostream& out, pair<L, R> const &val){

return (out << "(" << val.first << "," << val.second << ") ");

}

template<typename L, size_t N> ostream& operator << (ostream& out, array<L, N> const &cont){

out << "[ ";

for(auto&& elem : cont) _containerprint(out, elem);

return (out << "]");

}

template<class T> ostream& operator<<(ostream &out, ordered_set<T> const& S){

out << "{ ";

for(const auto& s:S) out << s << " ";

return (out << "}");

}

template<class L, class R, class chash = std::hash<L> > ostream& operator << (ostream &out, gp_hash_table<L, R, chash> const& M) {

out << "{ ";

for(const auto& m: M) out << "(" << m.first << ":" << m.second << ") ";

return (out << "}");

}

template<class P, class Q = vector<P>, class R = less<P> > ostream& operator << (ostream& out, priority_queue<P, Q, R> const& M){

static priority_queue<P, Q, R> U;

U = M;

out << "{ ";

while(!U.empty())

out << U.top() << " ", U.pop();

return (out << "}");

}

template<class P> ostream& operator << (ostream& out, queue<P> const& M){

static queue<P> U;

U = M;

out << "{ ";

while(!U.empty())

out << U.front() << " ", U.pop();

return (out << "}");

}

#define TRACE

#ifdef TRACE

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1>

void __f(const char* name, Arg1&& arg1){

cerr << name << " : " << arg1 << endl;

}

template <typename Arg1, typename... Args>

void __f(const char* names, Arg1&& arg1, Args&&... args){

const char* comma = strchr(names + 1, ',');

cerr.write(names, comma - names) << " : " << arg1<<" | ";

__f(comma+1, args...);

}

#else

#define trace(...) 1

#endif

/*/---------------------------RNG----------------------/*/

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

inline int64_t random_long(long long l = LLONG_MIN,long long r = LLONG_MAX){

uniform_int_distribution<int64_t> generator(l,r);

return generator(rng);

}

struct custom_hash { // Credits: https://codeforces.com/blog/entry/62393

static uint64_t splitmix64(uint64_t x) {

// http://xorshift.di.unimi.it/splitmix64.c

x += 0x9e3779b97f4a7c15;

x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;

x = (x ^ (x >> 27)) * 0x94d049bb133111eb;

return x ^ (x >> 31);

}

size_t operator()(uint64_t x) const {

static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();

return splitmix64(x + FIXED_RANDOM);

}

template<typename L, typename R>

size_t operator()(pair<L,R> const& Y) const{

static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();

return splitmix64(Y.first * 31ull + Y.second + FIXED_RANDOM);

}

};

/*/---------------------------Defines----------------------/*/

#define ll long long

#define endl "\n"

#define all(v) (v).begin(),(v).end()

/*/-----------------------Modular Arithmetic---------------/*/

const int mod = 1e9 + 7;

/*/-----------------------------Code begins----------------------------------/*/

void solve(){

string s, f;

cin >> s >> f;

int ans = 0;

for(auto e: s){

int a = (e - 'a');

int k = 26;

for(auto z: f){

int b = (z - 'a');

k = min(k,min((b - a + 26) % 26, (a - b + 26) % 26));

}

ans += k;

}

cout << ans << endl;

}

int main(){

// Use "set_name".max_load_factor(0.25);"set_name".reserve(512); with unordered set

// Or use gp_hash_table<X,null_type>

ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

cout << fixed << setprecision(25);

cerr << fixed << setprecision(10);

auto start = std::chrono::high_resolution_clock::now();

int t = 1;

cin >> t;

for(int i = 1; i <= t; ++i) {

cout << "Case #" << i << ": ";

solve();

}

auto stop = std::chrono::high_resolution_clock::now();

auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>(stop - start);

// cerr << "Time taken : " << ((long double)duration.count())/((long double) 1e9) <<"s "<< endl;

}