Last Updated: 25 Nov, 2021

Longest Prefix Which is Suffix

Moderate

Asked in companies

Solve now

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'.

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.

Solve now

Approaches

01 Approach

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 “”

Solve now

02 Approach

In this approach, we will create an ‘lps’ array, ‘lps[i]’, which will store the longest prefix which is also a suffix for the substring ‘str[0: i]’. We create a left and right pointer, where the left pointer points to the ending of the prefix and the right pointer will point to the current position.

If str[right] is equal to str[left] then we set lps[right] as lps[left] + 1, and increase the left pointer.

If they are not equal, then we know the prefix earlier is of length ‘str[left]’ therefore, we will move the left pointer to ‘str[left - 1]’, to check before the start of the current prefix.

Algorithm:

Initialise an ‘lps’ array of size equal to the length of the ‘str’.
Set leftPointer as 0
Set i as 1.
While i is less than length of ‘str’
- If str[i] is equal to s[leftPointer]
  - Increase leftPointer by 1
  - Set lps[i] as leftPointer
  - Increase i by 1
- Otherwise if leftPointer is not equal to 0
  - Set leftPointer as lps[leftPointer - 1]
- Otherwise, set lps[i] as 0 and increase i by 1.
return substr(str,0,lps[str.length()-1])

Solve now