Find The Longest Sequence Of Prefix Shared By All The Words In A String

Objective: Write an algorithm to find The Longest Sequence Of Prefix Shared By All The Words In A String. This interesting problem was asked in the Google interview for software engineer. This problem is bit tricky, it looks difficult but actually it is simple problem.

Input: A String

Output: The longest sequence of prefix common in all the words in a string

Example:

“Bedroom BedClock BedTable BedWall” => “Bed”

Approach:

  • Split the input by blank space and store it in arrA[].
  • Create int resultLen and store the first index string length in it (int resultLen = arrA[0].length())
  • Create another interger variable, int curr
  • Now run a loop in rest of the array.
  • Check if curr < resultLen and curr<length of current string in a loop
  • If so check if character at curr position matched in first index string and with the current string a loop, if so, increase curr by 1
  • Change resultLen = curr
  • Return substring of resultLen length

Complete Code:


Output:
Original String : Sumit Summation Summit Sum
Common Prefix is : Sum

 

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

  • Muthu

    Good start.
    But i see some code not appropriate. I believe if the code is run on this
    Sumit Muthu Summation Summit Sum, it will not give desired output. You need to tweak your while loop.
    while (curr < resultLen && curr < arrA[i].length()
    && arrA[0].charAt(curr) == arrA[1].charAt(curr))

    you have to keep track of prev and compare the curr with that, not just [0] and [1]

    • Sumit Jain

      Thanks Muthu for pointing it out, i had put “1” instead of “i”. Corrected it

      Sumit

  • Sumeet Vandakudri

    Your code fails for {“a”, “a”, “b”} The output should be “” but your code give “a” as output !
    Correct me if i am wrong!!

%d bloggers like this: