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:

public class LongestPrefixSequence {
private String[] arrA;
public LongestPrefixSequence(String[] arrA) {
this.arrA = arrA;
}
public String findPrefix() {
int resultLen = arrA[0].length();
int curr;
for (int i = 1; i < arrA.length; i++) {
curr = 0;
while (curr < resultLen && curr < arrA[i].length()
&& arrA[0].charAt(curr) == arrA[i].charAt(curr)) {
curr++;
}
resultLen = curr;
}
return arrA[0].substring(0, resultLen);
}
public static void main(String args[]) {
String x = "Sumit Summation Summit Sum";
String[] arrA = x.split(" ");
LongestPrefixSequence lp = new LongestPrefixSequence(arrA);
System.out.println("Original String : " + x);
System.out.println("Common Prefix is : " + lp.findPrefix());
}
}

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