Test results - Codility

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.

100%

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:

def 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.

Solution

Programming language used Python

Time spent on task 1 minutes

Notes

not defined yet

Code: 18:45:45 UTC, py, verify, result: Passed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(P, Q):
    from itertools import combinations

    # Step 1: Assign indices to each distinct letter
    letters = set(P + Q)
    letter_to_index = {c: i for i, c in enumerate(letters)}
    index_to_letter = {i: c for c, i in letter_to_index.items()}
    D = len(letter_to_index)

    # Step 2: Collect required letters (R) first
    R = set()
    for p, q in zip(P, Q):
        if p == q:
            R.add(letter_to_index[p])

    # Step 3: Collect edges where P[i] != Q[i] and neither P[i] nor Q[i] is in R
    edge_set = set()
    for p, q in zip(P, Q):
        if p != q:
            u = letter_to_index[p]
            v = letter_to_index[q]
            if u not in R and v not in R:
                if u > v:
                    u, v = v, u
                edge_set.add((u, v))

    # Step 4: Define G' nodes (excluding R)
    G_nodes = sorted(set(range(D)) - R)
    D_prime = len(G_nodes)
    node_map = {node: i for i, node in enumerate(G_nodes)}

    # Step 5: Assign edge indices
    edge_list = list(edge_set)
    E = len(edge_list)
    if E == 0:
        return len(R)  # No edges to cover

    # Step 6: Compute node cover masks
    node_cover_masks = [0] * D_prime
    for e, (u, v) in enumerate(edge_list):
        if u in node_map:
            node_cover_masks[node_map[u]] |= (1 << e)
        if v in node_map:
            node_cover_masks[node_map[v]] |= (1 << e)

    all_cover_mask = (1 << E) - 1  # All edges must be covered

    # Step 7: Recursive backtracking to find minimal vertex cover
    min_cover = D_prime  # Initialize with the maximum possible

    def backtrack(current_cover, covered_mask, k):
        nonlocal min_cover
        if covered_mask == all_cover_mask:
            if k < min_cover:
                min_cover = k
            return
        if k >= min_cover:
            return
        # Find the first uncovered edge
        first_uncovered = (covered_mask ^ all_cover_mask).bit_length() - 1
        if first_uncovered < 0 or first_uncovered >= E:
            if k < min_cover:
                min_cover = k
            return
        u, v = edge_list[first_uncovered]
        # Try including u
        if u in node_map:
            backtrack(current_cover | (1 << node_map[u]),
                      covered_mask | node_cover_masks[node_map[u]],
                      k + 1)
        # Try including v
        if v in node_map:
            backtrack(current_cover | (1 << node_map[v]),
                      covered_mask | node_cover_masks[node_map[v]],
                      k + 1)

    backtrack(0, 0, 0)
    return len(R) + min_cover

Analysis

▶

example1
First example test.

✔

▶

example2
Second example test.

✔

▶

example3
Third example test.

✔

▶

example4
Fourth example test.

✔

Code: 18:45:50 UTC, py, verify, result: Passed

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(P, Q):
    from itertools import combinations

    # Step 1: Assign indices to each distinct letter
    letters = set(P + Q)
    letter_to_index = {c: i for i, c in enumerate(letters)}
    index_to_letter = {i: c for c, i in letter_to_index.items()}
    D = len(letter_to_index)

    # Step 2: Collect required letters (R) first
    R = set()
    for p, q in zip(P, Q):
        if p == q:
            R.add(letter_to_index[p])

    # Step 3: Collect edges where P[i] != Q[i] and neither P[i] nor Q[i] is in R
    edge_set = set()
    for p, q in zip(P, Q):
        if p != q:
            u = letter_to_index[p]
            v = letter_to_index[q]
            if u not in R and v not in R:
                if u > v:
                    u, v = v, u
                edge_set.add((u, v))

    # Step 4: Define G' nodes (excluding R)
    G_nodes = sorted(set(range(D)) - R)
    D_prime = len(G_nodes)
    node_map = {node: i for i, node in enumerate(G_nodes)}

    # Step 5: Assign edge indices
    edge_list = list(edge_set)
    E = len(edge_list)
    if E == 0:
        return len(R)  # No edges to cover

    # Step 6: Compute node cover masks
    node_cover_masks = [0] * D_prime
    for e, (u, v) in enumerate(edge_list):
        if u in node_map:
            node_cover_masks[node_map[u]] |= (1 << e)
        if v in node_map:
            node_cover_masks[node_map[v]] |= (1 << e)

    all_cover_mask = (1 << E) - 1  # All edges must be covered

    # Step 7: Recursive backtracking to find minimal vertex cover
    min_cover = D_prime  # Initialize with the maximum possible

    def backtrack(current_cover, covered_mask, k):
        nonlocal min_cover
        if covered_mask == all_cover_mask:
            if k < min_cover:
                min_cover = k
            return
        if k >= min_cover:
            return
        # Find the first uncovered edge
        first_uncovered = (covered_mask ^ all_cover_mask).bit_length() - 1
        if first_uncovered < 0 or first_uncovered >= E:
            if k < min_cover:
                min_cover = k
            return
        u, v = edge_list[first_uncovered]
        # Try including u
        if u in node_map:
            backtrack(current_cover | (1 << node_map[u]),
                      covered_mask | node_cover_masks[node_map[u]],
                      k + 1)
        # Try including v
        if v in node_map:
            backtrack(current_cover | (1 << node_map[v]),
                      covered_mask | node_cover_masks[node_map[v]],
                      k + 1)

    backtrack(0, 0, 0)
    return len(R) + min_cover

Analysis

▶

example1
First example test.

✔

▶

example2
Second example test.

✔

▶

example3
Third example test.

✔

▶

example4
Fourth example test.

✔

Code: 18:45:54 UTC, py, final, score: 100

# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")

def solution(P, Q):
    from itertools import combinations

    # Step 1: Assign indices to each distinct letter
    letters = set(P + Q)
    letter_to_index = {c: i for i, c in enumerate(letters)}
    index_to_letter = {i: c for c, i in letter_to_index.items()}
    D = len(letter_to_index)

    # Step 2: Collect required letters (R) first
    R = set()
    for p, q in zip(P, Q):
        if p == q:
            R.add(letter_to_index[p])

    # Step 3: Collect edges where P[i] != Q[i] and neither P[i] nor Q[i] is in R
    edge_set = set()
    for p, q in zip(P, Q):
        if p != q:
            u = letter_to_index[p]
            v = letter_to_index[q]
            if u not in R and v not in R:
                if u > v:
                    u, v = v, u
                edge_set.add((u, v))

    # Step 4: Define G' nodes (excluding R)
    G_nodes = sorted(set(range(D)) - R)
    D_prime = len(G_nodes)
    node_map = {node: i for i, node in enumerate(G_nodes)}

    # Step 5: Assign edge indices
    edge_list = list(edge_set)
    E = len(edge_list)
    if E == 0:
        return len(R)  # No edges to cover

    # Step 6: Compute node cover masks
    node_cover_masks = [0] * D_prime
    for e, (u, v) in enumerate(edge_list):
        if u in node_map:
            node_cover_masks[node_map[u]] |= (1 << e)
        if v in node_map:
            node_cover_masks[node_map[v]] |= (1 << e)

    all_cover_mask = (1 << E) - 1  # All edges must be covered

    # Step 7: Recursive backtracking to find minimal vertex cover
    min_cover = D_prime  # Initialize with the maximum possible

    def backtrack(current_cover, covered_mask, k):
        nonlocal min_cover
        if covered_mask == all_cover_mask:
            if k < min_cover:
                min_cover = k
            return
        if k >= min_cover:
            return
        # Find the first uncovered edge
        first_uncovered = (covered_mask ^ all_cover_mask).bit_length() - 1
        if first_uncovered < 0 or first_uncovered >= E:
            if k < min_cover:
                min_cover = k
            return
        u, v = edge_list[first_uncovered]
        # Try including u
        if u in node_map:
            backtrack(current_cover | (1 << node_map[u]),
                      covered_mask | node_cover_masks[node_map[u]],
                      k + 1)
        # Try including v
        if v in node_map:
            backtrack(current_cover | (1 << node_map[v]),
                      covered_mask | node_cover_masks[node_map[v]],
                      k + 1)

    backtrack(0, 0, 0)
    return len(R) + min_cover

Analysis summary

The solution obtained perfect score.

Analysis

Detected time complexity:

O(2**A * A**2 + N) or O(2**A * A**2 + N * A**2)

Time complexity parameters:
A - size of the alphabet

▶

example1
First example test.

✔

▶

example2
Second example test.

✔

▶

example3
Third example test.

✔

▶

example4
Fourth example test.

✔

▶

small_simple
Small simple cases, A <= 6, N <= 10. Points x 2.

✔

0.012 s

▶

small_corner
Small corner cases, N <= 10.

✔

0.012 s

10.

0.012 s

▶

small_bipartite
Small tests where letter pairs form a bipartite graph, N <= 10.

✔

0.012 s

▶

small_freq
Small tests where some letters have big but similar frequencies, N <= 17, A <= 12.

✔

0.012 s

▶

medium_simple
Simple medium tests with small input and result diversity, N <= 30, A <= 10.

✔

▶

medium_sparse
Medium tests where letter pairs form sparse graphs, N <= 50. Points x 2.

✔

0.012 s

▶

medium_independent
Medium cases with many independent graphs in each case, N <= 50.

✔

▶

big_dense
Big tests where number of unique letter pairs exceeds 50. Points x 2.

✔

▶

big_random
Big random tests, N = MAX_N.

✔

▶

big_long
Some corner cases extended to big length, N <= MAX_N. Points x 3.

✔