-1

Problem Statements: In an interview I faced a coding challenge with this question which I could not figure out.

Given a string s contains lowercase alphabet, find the length of the Longest common Prefix of all substrings in O(n)

For example 
s = 'ababac' 
Then substrings are as follow: 
1: s(1, 6) = ababac 
2: s(2, 6) = babac 
3: s(3, 6) = abac 
4: s(4, 6) = bac 
5: s(5, 6) = ac 
6: s(6, 6) = c 

Now, The lengths of LCP of all substrings are as follow 

1: len(LCP(s(1, 6), s)) = 6 
2: len(LCP(s(2, 6), s)) = 0 
3: len(LCP(s(3, 6), s)) = 3 
4: len(LCP(s(4, 6), s)) = 0 
5: len(LCP(s(5, 6), s)) = 1 
6: len(LCP(s(6, 6), s)) = 0 

String contains only lowercase alphabates.

I found out some same question in this community but they are just problem statement the meaning could not define. This one

One of the leetcode problem is also somewhat like that which I understand perfectly and code: Longest common prefix But my question sounds like same but the main difference is all this type of question provide a array of string but in my question there is a single string and I have to find out longest common prefix from this string.

Can any one please explain me the problem properly what exactly this question looking for?

Mitch
  • 3,342
  • 2
  • 21
  • 31
Encipher
  • 1,370
  • 1
  • 14
  • 31
  • You have an array of `String`s: all substrings of `s`. By some observations, you can argue why you need only to consider Substrings of form `s(i, 6)` (and `i` in `[1, 6]`). – Turing85 Feb 28 '19 at 21:47
  • Peripherla question: how is your question `java`-related? – Turing85 Feb 28 '19 at 21:49

1 Answers1

1

You need to find the longest common substring between two strings. In each case, one of those is s, the original string. The other string is a right-end substring of s. These are the first list.

A few examples:

substring         common   len   reason
s(1, 6) = ababac  ababac    6     Comparing the string with itself yields the entire string
s(3, 6) = abac    aba       3     Only the first 3 characters match
s(4, 6) = bac     -none-    0     The first characters differ, so there is no common prefix.

Does that help?

Prune
  • 76,765
  • 14
  • 60
  • 81