We are given two strings P and Q, each consisting of N lowercase English letters. For each position in the strings, we have to choose one letter from either P or Q, in order to construct a new string S, such that the number of distinct letters in S is minimal. Our task is to find the number of distinct letters in the resulting string S.
For example, if P = "ca" and Q = "ab", S can be equal to: "ca", "cb", "aa" or "ab". String "aa" has only one distinct letter ('a'), so the answer is 1 (which is minimal among those strings).
Write a function:
function solution(P, Q);
that, given two strings P and Q, both of length N, returns the minimum number of distinct letters of a string S, that can be constructed from P and Q as described above.
Examples:
1. Given P = "abc", Q = "bcd", your function should return 2. All possible strings S that can be constructed are: "abc", "abd", "acc", "acd", "bbc", "bbd", "bcc", "bcd". The minimum number of distinct letters is 2, which be obtained by constructing the following strings: "acc", "bbc", "bbd", "bcc".
2. Given P = "axxz", Q = "yzwy", your function should return 2. String S must consist of at least two distinct letters in this case. We can construct S = "yxxy", where the number of distinct letters is equal to 2, and this is the only optimal solution.
3. Given P = "bacad", Q = "abada", your function should return 1. We can choose the letter 'a' in each position, so S can be equal to "aaaaa".
4. Given P = "amz", Q = "amz", your function should return 3. The input strings are identical, so the only possible S that can be constructed is "amz", and its number of distinct letters is 3.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..200,000];
- strings P and Q are both of length N;
- strings P and Q are made only of lowercase letters (a−z);
- strings P and Q contain a total of at most 20 distinct letters.
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(P, Q) {
const N = P.length;
const allLetters = new Set((P + Q).split(""));
const letters = Array.from(allLetters);
const total = letters.length;
let minCount = total;
// Перебираем все возможные комбинации букв (подмножества)
for (let mask = 1; mask < (1 << total); mask++) {
const subset = new Set();
for (let i = 0; i < total; i++) {
if (mask & (1 << i)) {
subset.add(letters[i]);
}
}
let valid = true;
for (let i = 0; i < N; i++) {
if (!subset.has(P[i]) && !subset.has(Q[i])) {
valid = false;
break;
}
}
if (valid) {
minCount = Math.min(minCount, subset.size);
}
}
return minCount;
}// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(P, Q) {
const N = P.length;
const allLetters = new Set((P + Q).split(""));
const letters = Array.from(allLetters);
const total = letters.length;
let minCount = total;
for (let mask = 1; mask < (1 << total); mask++) {
const subset = new Set();
for (let i = 0; i < total; i++) {
if (mask & (1 << i)) {
subset.add(letters[i]);
}
}
let valid = true;
for (let i = 0; i < N; i++) {
if (!subset.has(P[i]) && !subset.has(Q[i])) {
valid = false;
break;
}
}
if (valid) {
minCount = Math.min(minCount, subset.size);
}
}
return minCount;
}// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(P, Q) {
const N = P.length;
const allLetters = new Set((P + Q).split(""));
const letters = Array.from(allLetters);
const total = letters.length;
let minCount = total;
for (let mask = 1; mask < (1 << total); mask++) {
const subset = new Set();
for (let i = 0; i < total; i++) {
if (mask & (1 << i)) {
subset.add(letters[i]);
}
}
let valid = true;
for (let i = 0; i < N; i++) {
if (!subset.has(P[i]) && !subset.has(Q[i])) {
valid = false;
break;
}
}
if (valid) {
minCount = Math.min(minCount, subset.size);
}
}
return minCount;
}// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(P, Q) {
const N = P.length;
const allLetters = new Set((P + Q).split(""));
const letters = Array.from(allLetters);
const total = letters.length;
let minCount = total;
for (let mask = 1; mask < (1 << total); mask++) {
const subset = new Set();
for (let i = 0; i < total; i++) {
if (mask & (1 << i)) {
subset.add(letters[i]);
}
}
let valid = true;
for (let i = 0; i < N; i++) {
if (!subset.has(P[i]) && !subset.has(Q[i])) {
valid = false;
break;
}
}
if (valid) {
minCount = Math.min(minCount, subset.size);
}
}
return minCount;
}// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(P, Q) {
const N = P.length;
const allLetters = new Set((P + Q).split(""));
const letters = Array.from(allLetters);
const total = letters.length;
let minCount = total;
for (let mask = 1; mask < (1 << total); mask++) {
const subset = new Set();
for (let i = 0; i < total; i++) {
if (mask & (1 << i)) {
subset.add(letters[i]);
}
}
let valid = true;
for (let i = 0; i < N; i++) {
if (!subset.has(P[i]) && !subset.has(Q[i])) {
valid = false;
break;
}
}
if (valid) {
minCount = Math.min(minCount, subset.size);
}
}
return minCount;
}The following issues have been detected: timeout errors.
A - size of the alphabet
Small tests where some letters have big but similar frequencies, N <= 17, A <= 12.
Big random tests, N = MAX_N.
running time: 3.145 sec., time limit: 0.524 sec.
Some corner cases extended to big length, N <= MAX_N. Points x 3.
Killed. Hard limit reached: 6.000 sec.