Tasks Details
hard
1.
LetterCover
Given two strings P and Q, find the minimum number of distinct letters in a string constructed by selecting, for each position, a letter from either P or Q.
Task Score
73%
Correctness
100%
Performance
50%
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:
class Solution { public int solution(string P, string 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.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used C#
Time spent on task 1 minutes
Notes
not defined yet
Code: 22:32:09 UTC,
java,
autosave
Code: 22:32:16 UTC,
java,
autosave
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061
// you can also use imports, for example:
// import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public int solution(String P, String Q) {
int n = P.Length;
Dictionary<char, int> charToIndex = new Dictionary<char, int>();
int index = 0;
// Map each character to a unique index for bitmasking
for (int i = 0; i < n; i++) {
if (!charToIndex.ContainsKey(P[i]))
charToIndex[P[i]] = index++;
if (!charToIndex.ContainsKey(Q[i]))
charToIndex[Q[i]] = index++;
}
int maxMask = 1 << index; // There are 2^index possible states
int[] dp = new int[maxMask];
Array.Fill(dp, int.MaxValue);
dp[0] = 0; // Starting with no characters
// Evaluate each position
for (int i = 0; i < n; i++) {
int[] newDp = new int[maxMask];
Array.Fill(newDp, int.MaxValue);
for (int mask = 0; mask < maxMask; mask++) {
if (dp[mask] == int.MaxValue) continue;
int pMask = mask | (1 << charToIndex[P[i]]);
int qMask = mask | (1 << charToIndex[Q[i]]);
newDp[pMask] = Math.Min(newDp[pMask], dp[mask]);
newDp[qMask] = Math.Min(newDp[qMask], dp[mask]);
}
dp = newDp;
}
// Find the minimum number of distinct characters
int answer = int.MaxValue;
for (int mask = 0; mask < maxMask; mask++) {
if (dp[mask] < int.MaxValue) {
answer = Math.Min(answer, BitCount(mask));
}
}
return answer;
}
private int BitCount(int x) {
int count;
for (count = 0; x > 0; count++)
x &= x - 1; // This operation reduces x by the number of its lowest set bit
return count;
}
}
Code: 22:32:24 UTC,
cs,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(string P, string Q) {
int n = P.Length;
Dictionary<char, int> charToIndex = new Dictionary<char, int>();
int index = 0;
// Map each character to a unique index for bitmasking
for (int i = 0; i < n; i++) {
if (!charToIndex.ContainsKey(P[i]))
charToIndex[P[i]] = index++;
if (!charToIndex.ContainsKey(Q[i]))
charToIndex[Q[i]] = index++;
}
int maxMask = 1 << index; // There are 2^index possible states
int[] dp = new int[maxMask];
Array.Fill(dp, int.MaxValue);
dp[0] = 0; // Starting with no characters
// Evaluate each position
for (int i = 0; i < n; i++) {
int[] newDp = new int[maxMask];
Array.Fill(newDp, int.MaxValue);
for (int mask = 0; mask < maxMask; mask++) {
if (dp[mask] == int.MaxValue) continue;
int pMask = mask | (1 << charToIndex[P[i]]);
int qMask = mask | (1 << charToIndex[Q[i]]);
newDp[pMask] = Math.Min(newDp[pMask], dp[mask]);
newDp[qMask] = Math.Min(newDp[qMask], dp[mask]);
}
dp = newDp;
}
// Find the minimum number of distinct characters
int answer = int.MaxValue;
for (int mask = 0; mask < maxMask; mask++) {
if (dp[mask] < int.MaxValue) {
answer = Math.Min(answer, BitCount(mask));
}
}
return answer;
}
private int BitCount(int x) {
int count;
for (count = 0; x > 0; count++)
x &= x - 1; // This operation reduces x by the number of its lowest set bit
return count;
}
}
Code: 22:32:31 UTC,
cs,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
using System;
// you can also use other imports, for example:
using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(string P, string Q) {
int n = P.Length;
Dictionary<char, int> charToIndex = new Dictionary<char, int>();
int index = 0;
// Map each character to a unique index for bitmasking
for (int i = 0; i < n; i++) {
if (!charToIndex.ContainsKey(P[i]))
charToIndex[P[i]] = index++;
if (!charToIndex.ContainsKey(Q[i]))
charToIndex[Q[i]] = index++;
}
int maxMask = 1 << index; // There are 2^index possible states
int[] dp = new int[maxMask];
Array.Fill(dp, int.MaxValue);
dp[0] = 0; // Starting with no characters
// Evaluate each position
for (int i = 0; i < n; i++) {
int[] newDp = new int[maxMask];
Array.Fill(newDp, int.MaxValue);
for (int mask = 0; mask < maxMask; mask++) {
if (dp[mask] == int.MaxValue) continue;
int pMask = mask | (1 << charToIndex[P[i]]);
int qMask = mask | (1 << charToIndex[Q[i]]);
newDp[pMask] = Math.Min(newDp[pMask], dp[mask]);
newDp[qMask] = Math.Min(newDp[qMask], dp[mask]);
}
dp = newDp;
}
// Find the minimum number of distinct characters
int answer = int.MaxValue;
for (int mask = 0; mask < maxMask; mask++) {
if (dp[mask] < int.MaxValue) {
answer = Math.Min(answer, BitCount(mask));
}
}
return answer;
}
private int BitCount(int x) {
int count;
for (count = 0; x > 0; count++)
x &= x - 1; // This operation reduces x by the number of its lowest set bit
return count;
}
}
Analysis
Code: 22:32:40 UTC,
cs,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
using System;
// you can also use other imports, for example:
using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(string P, string Q) {
int n = P.Length;
Dictionary<char, int> charToIndex = new Dictionary<char, int>();
int index = 0;
// Map each character to a unique index for bitmasking
for (int i = 0; i < n; i++) {
if (!charToIndex.ContainsKey(P[i]))
charToIndex[P[i]] = index++;
if (!charToIndex.ContainsKey(Q[i]))
charToIndex[Q[i]] = index++;
}
int maxMask = 1 << index; // There are 2^index possible states
int[] dp = new int[maxMask];
Array.Fill(dp, int.MaxValue);
dp[0] = 0; // Starting with no characters
// Evaluate each position
for (int i = 0; i < n; i++) {
int[] newDp = new int[maxMask];
Array.Fill(newDp, int.MaxValue);
for (int mask = 0; mask < maxMask; mask++) {
if (dp[mask] == int.MaxValue) continue;
int pMask = mask | (1 << charToIndex[P[i]]);
int qMask = mask | (1 << charToIndex[Q[i]]);
newDp[pMask] = Math.Min(newDp[pMask], dp[mask]);
newDp[qMask] = Math.Min(newDp[qMask], dp[mask]);
}
dp = newDp;
}
// Find the minimum number of distinct characters
int answer = int.MaxValue;
for (int mask = 0; mask < maxMask; mask++) {
if (dp[mask] < int.MaxValue) {
answer = Math.Min(answer, BitCount(mask));
}
}
return answer;
}
private int BitCount(int x) {
int count;
for (count = 0; x > 0; count++)
x &= x - 1; // This operation reduces x by the number of its lowest set bit
return count;
}
}
Analysis
Code: 22:32:44 UTC,
cs,
final,
score:
73
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
using System;
// you can also use other imports, for example:
using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(string P, string Q) {
int n = P.Length;
Dictionary<char, int> charToIndex = new Dictionary<char, int>();
int index = 0;
// Map each character to a unique index for bitmasking
for (int i = 0; i < n; i++) {
if (!charToIndex.ContainsKey(P[i]))
charToIndex[P[i]] = index++;
if (!charToIndex.ContainsKey(Q[i]))
charToIndex[Q[i]] = index++;
}
int maxMask = 1 << index; // There are 2^index possible states
int[] dp = new int[maxMask];
Array.Fill(dp, int.MaxValue);
dp[0] = 0; // Starting with no characters
// Evaluate each position
for (int i = 0; i < n; i++) {
int[] newDp = new int[maxMask];
Array.Fill(newDp, int.MaxValue);
for (int mask = 0; mask < maxMask; mask++) {
if (dp[mask] == int.MaxValue) continue;
int pMask = mask | (1 << charToIndex[P[i]]);
int qMask = mask | (1 << charToIndex[Q[i]]);
newDp[pMask] = Math.Min(newDp[pMask], dp[mask]);
newDp[qMask] = Math.Min(newDp[qMask], dp[mask]);
}
dp = newDp;
}
// Find the minimum number of distinct characters
int answer = int.MaxValue;
for (int mask = 0; mask < maxMask; mask++) {
if (dp[mask] < int.MaxValue) {
answer = Math.Min(answer, BitCount(mask));
}
}
return answer;
}
private int BitCount(int x) {
int count;
for (count = 0; x > 0; count++)
x &= x - 1; // This operation reduces x by the number of its lowest set bit
return count;
}
}
Analysis summary
The following issues have been detected: timeout errors.
Analysis
Detected time complexity:
O(2**A * N)
Time complexity parameters:
A - size of the alphabet
A - size of the alphabet
expand all
Correctness tests
1.
0.016 s
OK
2.
0.016 s
OK
3.
0.016 s
OK
4.
0.016 s
OK
5.
0.016 s
OK
6.
0.016 s
OK
7.
0.016 s
OK
1.
0.016 s
OK
2.
0.016 s
OK
3.
0.016 s
OK
4.
0.020 s
OK
5.
0.016 s
OK
6.
0.016 s
OK
7.
0.016 s
OK
8.
0.016 s
OK
9.
0.016 s
OK
10.
0.016 s
OK
1.
0.016 s
OK
2.
0.016 s
OK
3.
0.016 s
OK
4.
0.016 s
OK
5.
0.016 s
OK
6.
0.020 s
OK
7.
0.016 s
OK
small_freq
Small tests where some letters have big but similar frequencies, N <= 17, A <= 12.
Small tests where some letters have big but similar frequencies, N <= 17, A <= 12.
✔
OK
1.
0.016 s
OK
2.
0.016 s
OK
3.
0.016 s
OK
4.
0.020 s
OK
5.
0.020 s
OK
6.
0.020 s
OK
7.
0.016 s
OK
8.
0.020 s
OK
expand all
Correctness/performance tests
1.
0.016 s
OK
2.
0.016 s
OK
3.
0.016 s
OK
1.
0.020 s
OK
2.
0.020 s
OK
3.
0.024 s
OK
4.
0.024 s
OK
5.
0.020 s
OK
6.
0.020 s
OK
1.
0.028 s
OK
2.
0.032 s
OK
3.
0.020 s
OK
4.
0.028 s
OK
5.
0.036 s
OK
expand all
Performance tests
1.
0.048 s
OK
2.
0.028 s
OK
3.
0.088 s
OK
1.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
2.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
3.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
big_long
Some corner cases extended to big length, N <= MAX_N. Points x 3.
Some corner cases extended to big length, N <= MAX_N. Points x 3.
✘
TIMEOUT ERROR
Killed. Hard limit reached: 6.000 sec.
Killed. Hard limit reached: 6.000 sec.
1.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
2.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.
3.
0.180 s
OK
4.
6.000 s
TIMEOUT ERROR,
Killed. Hard limit reached: 6.000 sec.