FastPrep
Problem · String

Unaligned Dedupe

Learn this problem
● MediumRubrikINTERNOA

Problem statement

You are given n lowercase strings, each of length m. Choose a block length l with l >= k, and split every string from left to right into non-overlapping blocks of length l. The last block may be shorter.

A block can be replaced by a zero-cost reference when an identical earlier block exists either in the same string or in the immediately previous string. Blocks may occur at different block positions in those strings.

The saving contributed by a referenced block equals its number of characters. Find the block length that maximizes total savings. If several lengths tie, choose the smallest.

Return [best block length, maximum characters saved].

Function

unalignedDedupe(strings: String[], m: int, k: int) → int[]

Examples

Example 1

strings = ["aand", "ndaa", "bend"]m = 4k = 1return = [1, 7]

With block length 1, one character is saved in the first string, four in the second, and two in the third, for a total of 7.

Example 2

strings = ["abcdef", "defabc", "abdfea"]m = 6k = 2return = [3, 6]

With block length 3, both blocks of the second string match blocks of the first string, saving 6 characters.

Constraints

  • 1 <= n <= 1.5 * 106
  • 1 <= m <= 1.5 * 106
  • 1 <= n*m <= 1.5 * 106
  • 1 <= k <= m

    • More Rubrik problems

    drafts saved locally
    public int[] unalignedDedupe(String[] strings, int m, int k) {
  // write your code here
}
    strings["aand", "ndaa", "bend"]
    m4
    k1
    expected[1, 7]
    checking account