N3 - Editorial

Problem Link - K-important Strings

Problem Statement -

You are given a set of N strings S0, S1, …, SN-1. These strings consist of only lower case characters a..z and have the same length L.

A string H is said to be K-important if there are at least K strings in the given set of N strings appearing at K different positions in H. These K strings need not to be distinct.

Your task is to find the shortest K-important string. If there are more than one possible solution, your program can output any of them.

Approach

The solution involves calculating overlaps and using dynamic programming (DP) to find the shortest concatenated string.

  1. Calculate the overlap between every pair of strings using the overlap function, which determines how much of one string aligns with the end of another. Store the results in the olap matrix.

  2. Initialize the DP table bf[i][j], where bf[i][j] represents the shortest length of a K- important string using i+1 strings and ending with string j. Set bf[0][j]=L for all strings j.

  3. For each i from 1 to K−1, compute bf[i][j] by iterating over all possible previous strings k. Calculate the new length by adding L−olap[k][j] to bf[i−1][k]. Update bf[i][j] with the minimum value and store the previous string k in the previous table for reconstruction.

  4. Find the string index with the shortest length in bf[K−1][j]. Backtrack through the previous table to reconstruct the sequence of strings forming the shortest $K-$important string.

  5. Compute the final concatenated string by appending parts of strings based on the overlap and print the result. Additionally, print the sequence of indices and their positions in the concatenated string.

Time Complexity

The time complexity is O(N^2 \cdot K \cdot L) due to overlap calculation and DP transitions over N strings for K iterations.

Space Complexity

The space complexity is O(N^2 + K \cdot N) to store the overlap matrix and the DP tables.