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

Run This Code

Code:

Output:

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

Also Read:

- Find two elements whose sum is closest to zero Medium
- Find the subarray with sum to a Given Value. Medium
- Find duplicates in an given array in O(n) time and O(1) extra space. Medium
- Dynamic Programming - Longest Increasing Subsequence Medium
- Magic Index - Find Index In Sorted Array Such That A[i] = i. Beginner
- Search an Element in a Rotated Sorted Array Medium
- Find three smallest elements in a given array Beginner
- Backtracking - N Queens Problem - Better Solution Hard