D_Coder_03's blog

Interview bit Problem
By D_Coder_03, history, 4 years ago, In English

Defining substring For a string P with characters P1, P2 ,…, Pq, let us denote by P[i, j] the substring Pi, Pi+1 ,…, Pj.

Defining longest common prefix LCP(S1, S2 ,…, SK), is defined as largest possible integer j such that S1[1, j] = S2[1, j] = … = SK[1, j].

You are given an array of N strings, A1, A2 ,…, AN and an integer K. Count how many indices (i, j) exist such that 1 ≤ i ≤ j ≤ N and LCP(Ai, Ai+1 ,…, Aj) ≥ K. Print required answer modulo 109+7.

Note that K does not exceed the length of any of the N strings. K <= min(len(A_i)) for all i

For example,

A = ["ab", "ac", "bc"] and K=1.

LCP(A[1, 1]) = LCP(A[2, 2]) = LCP(A[3, 3]) = 2 LCP(A[1, 2]) = LCP("ab", "ac") = 1 LCP(A[1, 3]) = LCP("ab", "ac", "bc") = 0 LCP(A[2, 3]) = LCP("ac", "bc") = 0

So, answer is 4. Return your answer % MOD = 1000000007

Constraints 1 ≤ Sum of length of all strings ≤ 5*10^5 Strings consist of small alphabets only.

Can someone tell me how would I approach this problem?

  • Vote: I like it
  • +25
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Can you share the link to the problem?

I have a solution which I would like to try. Sort the list of the strings and calculate lcp(ai,ai-1) and keep a pointer at ai-1 if it is greater than k and if you encounter lcp(ai,ai-1) less than k change the pointer to next index where you will find lcp at least k and add difference in pointers accordingly.

sorry for my bad english.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It was a test problem bro so I just managed to copy the question before it came to an end. Even I also thought like your solution but wasn't able to execute it though.

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

You can just compare the first $$$k$$$ characters of every adjacent pair of strings. So you can just remove the rest of the characters. Now let's say you got $$$A_i = A_{i+1} ... = A_j$$$, you can add $$$\binom{j-i+1}{2}$$$ to the total answer. Since each string is being compared twice at most, the time complexity is $$$O(\sum |A|)$$$. Edit : Set answer to $$$n$$$ initially.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you elaborate your solution a little?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Let's take an example, $$$A = "ab", "ac", "bc"$$$, K=1. Let's keep only the first $$$k$$$ characters of all strings in $$$A$$$. So $$$A = "a", "a", "c"$$$. Now the consecutive ranges of equal elements are $$$(1,2), (3,3)$$$. So the answer is $$$n + \binom{2 - 1 + 1}{2} + \binom{3- 3 + 1}{2}$$$. That is because in a range of length of $$$l$$$, there are $$$\binom{l}{2}$$$ subarrays of length $$$>1$$$. We add $$$n$$$ for single length subarrays.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Thank you, understood your approach, great one!!

        → Reply