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


“Bedroom BedClock BedTable BedWall” => “Bed”


  • 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:

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.

You may also like...

3 Responses

  1. Muthu says:

    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]

  2. Sumeet Vandakudri says:

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

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: