Longest Prefix Which is Suffix

Moderate
0/80
profile
Contributed by
26 upvotes
Asked in companies
Expedia GroupFlipkart limited

Problem statement

You are given a string ‘str’.


Find the longest prefix in the string which is also a suffix of the string, excluding the string itself.


If there's no such string return an empty string "".


Example: 
Input: ‘str’ = ‘ababcdabab’ 

Output: 'abab'

Explanation:
Here the prefix ‘abab’ is equal to the suffix ‘abab’. The length of the prefix is 4. There's no other prefix that has length > 4 and is also present as a suffix. Hence the answer is 'abab'.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of input contains a string ‘str’ representing the input string.


Output Format: 
Return a single integer representing the length of the largest prefix which is also a suffix. If there's no such string return an empty string.


Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function. '-1' will be printed for returned strings that are empty.
Sample Input 1:
aaaaabaa


Expected Answer:
"aa"


Output on console:
aa


Explanation of Sample Input 1:
For this test case, ‘str’ = ‘aaaaabaa’. Here the prefix ‘aa’ is equal to the suffix ‘aa’. The length of the prefix is 2. There's no other prefix with length > 2 which is also present as a suffix. Hence the answer is 'aa'.


Sample Input 2:
aab


Expected Answer:

""

Output on console:
-1


Expected Time Complexity:
Try to do this in O(n), where 'n' is the length of string 'str'.


Constraints:
1 <= |str| <= 10^6

All the characters of ‘str’ are lower case English alphabets.
Time Limit: 1 sec
Hint

 Try by checking all the possible prefixes.

Approaches (2)
Brute-Force

In this approach, we will check all the possible prefixes of the given string. Since we have to find the longest non-overlapping prefix, we will start from the prefix of ‘N/2’ length, where ‘N’ is the length of the string, and then we keep decreasing the prefix, length as long as it doesn’t match with the suffix of the same length.

 

Algorithm:

  • In the isEqual(str1, str2) function:
    • Takes two string and returns a True if all characters match in two strings, ‘str1’ and ‘str2’
  • In the given function:
    • Set N as the length of ‘str’
    • Iterate preLen through N-1 to 0
      • Set prefix as substring of str from 0 to preLen - 1
      • Set suffix as substring of str from n - preLen to n - 1
      • If suffix is equal to prefix then return prefix
    • If the function reaches out of the loop return “”
Time Complexity

O(N^2), Where N is the length of the string.

 

We iterate over all the prefixes and suffixes which will cost O(N/2) time, to compare each prefix to suffix will cost O(N) time. Hence the final time complexity is O(N^2)

Space Complexity

O(N), Where N is the length of the string.

 

We are storing the prefix and suffix for each iteration of the loop which will take O(N) space. Hence the final space complexity is O(N).

Code Solution
(100% EXP penalty)
Longest Prefix Which is Suffix
Full screen
Console